传送门:https://codeforces.com/problemset/problem/797/C
题意:给你一个字符串s,你可以把字符串s的第一个字符串给t,也可以把字符串t的最后一个字符给u,t和u初始时为空串,要你求字典序最小的u
题解:仔细读这个操作,是不是发现字符串s和t有这样一个性质,s的第一个给t,然后t的最后一个给u的末尾,那么s给t 的元素就是先进后出,那么t就是一个栈,到这里我们就明了了,我们需要 用一个栈来维护这个序列,那么怎么让字典序最小呢,我们将字符串从后往前扫一遍,保存每个位置可以放的最小的字符,然后再从前往后,用一个栈来存字符,如果遇到满足小于等于当前位置的最小字符的话就输出,出栈,否则就进栈,最后将栈里面的元素输出就行(仔细想想 有点后缀预处理的味道?
代码如下:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5+5; string str; int a[maxn]; int minn[maxn]; int main(){ while(cin>>str){ int n=str.length(); for(int i=0;i<n;i++){ a[i]=str[i]; } //用minn来保存当前位置可以放的最小的字符 for(int i=n-1;i>=0;i--){ if(i==n-1) minn[i]=a[i]; else minn[i]=min(minn[i+1],a[i]); } // for(int i=0;i<n;i++){ // cout<<(char)minn[i]; // } stack<char> ans; for(int i=0;i<n;i++){ if(ans.size()==0){ ans.push(str[i]); }else{ while(!ans.empty()){ char u=ans.top(); //如果栈里面的元素小于等于当前位置可以放的字符的话 //那么这个位置一定是最优的 if(u<=minn[i]){ printf("%c",u); ans.pop(); }else{ break; } } ans.push(str[i]); } } while(!ans.empty()){ printf("%c",ans.top()); ans.pop(); } } }