昆明双鼎网站制作,seo搜索引擎实战详解,php网站开发程序编译软件,观止网站建设题干#xff1a;
CSL 以前不会字符串算法#xff0c;经过一年的训练#xff0c;他还是不会……于是他打算向你求助。
给定一个字符串#xff0c;只含有可打印字符#xff0c;通过删除若干字符得到新字符串#xff0c;新字符串必须满足两个条件#xff1a;
原字符串中…题干
CSL 以前不会字符串算法经过一年的训练他还是不会……于是他打算向你求助。
给定一个字符串只含有可打印字符通过删除若干字符得到新字符串新字符串必须满足两个条件
原字符串中出现的字符新字符串也必须包含。新字符串中所有的字符均不相同。新字符串的字典序是满足上面两个条件的最小的字符串。
输入描述:
仅一行有一个只含有可打印字符的字符串 s。
|s|≤105|s|≤105
输出描述:
在一行输出字典序最小的新字符串。
示例1
输入
复制
bab
输出
复制
ab
示例2
输入
复制
baca
输出
复制
bac
备注:
ASCII字符集包含 94 个可打印字符(0x21 - 0x7E)不包含空格。
解题报告 这题是类似单调栈的思想只不过弹出的时候要判断一下是否后面还有改数字。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includestack
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 1e5 5;
string s;
bool vis[MAX];
int bk[555],tot;
stackchar sk;
int main() {cins;int len s.size();s s;for(int i 1; ilen; i) {bk[s[i]];}string ans;int cur 1,pos 1;for(int i 1; ilen; i) {char tar s[i];bk[tar]--;if(vis[tar]) continue;while( sk.size() bk[sk.top()] tar sk.top()) {vis[sk.top()] 0;sk.pop();ans.pop_back();}ans tar;sk.push(tar);vis[tar] 1;}cout ans endl;return 0 ;
}
//bcdddbca
