Minimal string CodeForces - 797C

2018-06-17 21:55:19来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Common Divisors CodeForces - 182D || kmp最小循环节

下一篇:2017年腾讯 秋招软件开发笔试编程题回忆版