Minimal string CodeForces

题意：有一个字符串s和空串t和u，每次操作可以将s的第一个字符取出并删除然后放到t的最后，或者将t的最后一个字符取出并删除然后放到u的最后。要求使得最后s和t均为空串。求字典序最小的可能得到的u。

分析：这道题的操作相当于“将s中字符按从左到右顺序入栈，在任意次的入栈后可以进行任意次的出栈”。显然，最后得到字符串的长度一定是相等的，因此字典序最小就是要前面的尽可能的小。因此可以用一个数组分别记录还未入栈的'a'到'z'的个数，按照'a'到'z'的顺序去找。每找一个字符c的第一步是：首先在栈顶找出所有大于等于c的字符，出栈并输出。之后的操作只有在还有未入栈的c时才去做：在原串中还未入栈的部分从前往后找c，把其他字符入栈，把c直接输出（相当于入栈后直接出栈、输出），直到所有未入栈的c没有了。找完'z'后，再将所有栈中剩余字符出栈并输出即可。

 #include<cstdio>

 #include<cstring>

 char s[];

 int a[],now,top;

 char st[];

 //曾经误将top写成char类型导致re

 int main()

 {

     scanf("%s",s);

     int i,len=strlen(s);

     for(i=;i<len;i++)

         a[s[i]]++;

     for(i='a';i<='z';i++)

     {

         while(top>&&st[top]<=i)

         {

             printf("%c",st[top]);

             top--;

         }

         while(a[i])

         {

             while(s[now]!=i&&now<len)

             {

                 st[++top]=s[now];

                 a[s[now]]--;

                 now++;

             }

             while(s[now]==i&&now<len)

             {

                 printf("%c",i);

                 a[i]--;

                 now++;

             }

         }

     }

     while(top>)

     {

         printf("%c",st[top--]);

     }

     return ;

 }

巴特西

Minimal string CodeForces - 797C

最新文章

热门文章