题意:给出string s长度<=1e5, op1:把s的第一个字符移动到t末尾.op2:把t最后一个字符移到u末尾,求u能得到的最小字典序? 思路： 用逆序维护一个数组Min，Min是用来表示其元素后边最小的字符，用Min是用来跟栈顶元素比较，如果栈顶元素小于等于的话就输出栈顶元素，继续用栈顶元素跟Min比较，直到不符合条件为止 。 同时每个字符都在操作结束后入栈。
#include<stdio.h> #include<string.h> #include<stack> #include<algorithm> using namespace std; const int MAXN = 1e5+7; char s[MAXN]; int Min[MAXN]; int main() { while(~scanf("%s",&s)) { int n=strlen(s); memset(Min,0,sizeof(Min)); for(int i=n-1;i>=0;i--) { int a=s[i]; if(i==n-1) Min[i]=a; else Min[i]=min(Min[i+1],a);//min只能是两个类型比较 } stack<char>sta; for(int i=0;i<n;i++) { if(sta.empty()) sta.push(s[i]); else { while(!sta.empty()) //这个栈的判断必须写，因为不写就会出现栈顶元素底下的元素比要加入的元素小却没被输出的情况 { char c=sta.top(); if(c<=Min[i]) { printf("%c",c); sta.pop(); } else break; } sta.push(s[i]); } } while(!sta.empty()) { char c=sta.top(); printf("%c",c); sta.pop(); } printf("\n"); } }