http://codeforces.com/contest/797/problem/C
给定一个长度不超过 105 的字符串 s, 以及两个空字符串t 和 u。定义两种合法操作:
- 将 s 串的第一个字符移动到字符串 t 的末尾。
- 将 t 串的最后一个字符移动到字符串 u 的末尾。
我们希望将 s 和 t 都变为空串并且使得串 u 字典序尽可能的小。
你需要写一个代码求出最小的字典序。
第一个想法是每次找剩余的最小与堆栈的顶端比较。
#include<stdio.h>
#include<stack>
#include<string.h>
#include<algorithm>
using namespace std;
char s[100005];int min(char s[],int cnt,int n)
{int i,j,k;char min;min=s[cnt];int flag=cnt;for(i=cnt+1;i<n;i++){if(s[i]<min){min=s[i];flag=i;}}return flag;
}
int main()
{memset(s,0,sizeof(s));stack<char>t;scanf("%s",s);//printf("%d",strlen(s));int n=strlen(s);int i,j,k;for(i=0;i<n;i++){int cnt=min(s,i,n);//printf("%d",cnt);if(!t.empty()){if(t.top()>s[cnt]){for(j=i;j<cnt;j++){t.push(s[j]);}printf("%c",s[cnt]);i=cnt; }if(t.top()<=s[cnt]){printf("%c",t.top());t.pop();i--;}}else{for(j=i;j<cnt;j++){t.push(s[j]);}printf("%c",s[cnt]);i=cnt; }}while(!t.empty()){printf("%c",t.top());t.pop();}}复杂度大约是nlgn，然后超时了……
第二个思路是统计每个字母出现的次数，然后从第一个开始遍历
/**/
#include<stdio.h>
#include<stack>
#include<string.h>
#include<algorithm>
using namespace std;
char a[100005];
int main()
{while(scanf("%s",a)==1){int b[30];stack<char>c;memset(b,0,sizeof(b));int lena=strlen(a);int i,j,k;for(i=0;i<lena;i++){b[a[i]-'a']++;//保存字母出现的个数}i=0;while(a[i]){int k=26;if(!c.empty()){k=c.top()-'a';}for(j=0;j<26;j++){if(b[j])break;//尽可能小}k=min(j,k);寻找最小值while(1){if(!c.empty()&&c.top()-'a'==k)//找到了{break;}b[a[i]-'a']--;没找到入栈c.push(a[i++]);if(a[i]=='\0') break;}if(!c.empty())//出栈{printf("%c",c.top());c.pop();}}while(!c.empty()) { char d=c.top(); c.pop(); printf("%c",d); } printf("\n");}
}