上海高校程序设计联赛 D-CSL的字符串 栈模拟

题目链接：https://ac.nowcoder.com/acm/contest/551/D

ASCII码表示的字符转换成整数实测不超过200（具体多少懒得查了）

分析：要求总的字典序最小，那就让最小的字符尽可能放在前面，除非最小的字符前面比它大的字符存在只有一个的情况，这种情况删掉就不满足包含原串所有字符的要求了，就不能删，其他的后面还有的字符就可以随便删，由此我们用栈来实现这个操作。

先用book数组记录每个字符出现的次数，然后从头开始遍历字符串，每遍历到一个，便将对应的book数组减一，同时看栈里是否有这个字符，有就跳过。没有的话进一步判断当前字符是否比栈顶要小并且栈顶字符在后面还存在，如果是的话栈顶元素就退栈，持续这个操作直到栈顶元素更小或者之后栈顶元素不存在，把该元素压进去即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=1<<30;
const int maxn=1e5+7;
const double pi=acos(-1);
const int mod=1e9+7;
int book[95],vis[95];
char ans[maxn];
int main(){
    string s;cin>>s;
    int len=s.length();
    for(int i=0;i<len;i++){
        book[s[i]]++;
    }
    int cnt=0;
    for(int i=0;i<len;i++){
        book[s[i]]--;
        if(!vis[s[i]]){
            vis[s[i]]=1;
            while(cnt&&book[ans[cnt]]&&s[i]<ans[cnt]){
                vis[ans[cnt]]=0;
                cnt--;
            }
            ans[++cnt]=s[i];
        }
    }
    for(int i=1;i<=cnt;i++)printf("%c",ans[i]);
    cout<<endl;
    return 0;
}