Minimal string CodeForces - 797C
2018-06-17 21:55:19来源:未知 阅读 ()
Minimal string CodeForces - 797C
题意:有一个字符串s和空串t和u,每次操作可以将s的第一个字符取出并删除然后放到t的最后,或者将t的最后一个字符取出并删除然后放到u的最后。要求使得最后s和t均为空串。求字典序最小的可能得到的u。
分析:这道题的操作相当于“将s中字符按从左到右顺序入栈,在任意次的入栈后可以进行任意次的出栈”。显然,最后得到字符串的长度一定是相等的,因此字典序最小就是要前面的尽可能的小。因此可以用一个数组分别记录还未入栈的'a'到'z'的个数,按照'a'到'z'的顺序去找。每找一个字符c的第一步是:首先在栈顶找出所有大于等于c的字符,出栈并输出。之后的操作只有在还有未入栈的c时才去做:在原串中还未入栈的部分从前往后找c,把其他字符入栈,把c直接输出(相当于入栈后直接出栈、输出),直到所有未入栈的c没有了。找完'z'后,再将所有栈中剩余字符出栈并输出即可。
1 #include<cstdio> 2 #include<cstring> 3 char s[100100]; 4 int a[200],now,top; 5 char st[100100]; 6 //曾经误将top写成char类型导致re 7 int main() 8 { 9 scanf("%s",s); 10 int i,len=strlen(s); 11 for(i=0;i<len;i++) 12 a[s[i]]++; 13 for(i='a';i<='z';i++) 14 { 15 while(top>0&&st[top]<=i) 16 { 17 printf("%c",st[top]); 18 top--; 19 } 20 while(a[i]) 21 { 22 while(s[now]!=i&&now<len) 23 { 24 st[++top]=s[now]; 25 a[s[now]]--; 26 now++; 27 } 28 while(s[now]==i&&now<len) 29 { 30 printf("%c",i); 31 a[i]--; 32 now++; 33 } 34 } 35 } 36 while(top>0) 37 { 38 printf("%c",st[top--]); 39 } 40 return 0; 41 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 复习C++语法--string与string_view 2020-05-28
- STL之<string> 2020-04-05
- 【题解】Building Strings Gym - 102152E 2020-03-31
- CodeForces 1326E - Bombs 2020-03-25
- CodeForces 1320D - Reachable Strings 2020-03-20
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash