“新智认知”杯上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛 D CSL 的字符串

“新智认知”杯上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛 D CSL 的字符串

题目链接：

源自牛客网

这题现场赛的时候没做出来，出来问了一下大佬，两个字：“贪心”

显然，所有满足一二条件以后的字符串的长度都是一样的，唯一不同的是他们的字典序。

显然，我们想着尽可能地把字典序小的字符放在前面，字典序大地放在后面。按照这个原则我们对源字符串进行删减，但是，我们再删地时候还要考虑删掉地字符在后面是否还会再次出现（若后面没有了，这个就不能删）。

综合以上分析，我们选择“贪心+栈”解题。

附上代码：

#include <iostream>
#include <cstring>
#include <string>
#include <stack>
using namespace std;int vis[100005], use[100005];
stack <char> st;
int main()
{string str;cin >> str;memset(vis, 0, sizeof(vis));memset(use, 0, sizeof(use));for (int i = 0; i < str.length(); i++){use[str[i]]++;}st.push(str[0]);vis[str[0]] = 1;--use[str[0]];for (int i = 1; i < str.length(); i++){if (!vis[str[i]]){use[str[i]]--;                              //对当前字符分析一次，该字符就要少一次while (!st.empty() && str[i] < st.top() && p()]>0){p()] = 0;st.pop();}                                            //核心步骤，比较并删减st.push(str[i]);vis[str[i]] = 1;}}string str2;while (!pty()){str2 += st.top();st.pop();}for (int i = str2.length() - 1; i >= 0; i--){cout << str2[i];}cout << endl;str2 = "";
}