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

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

链接：
来源：牛客网

题目描述

CSL 以前不会字符串算法，经过一年的训练，他还是不会……于是他打算向你求助。

给定一个字符串，只含有可打印字符，通过删除若干字符得到新字符串，新字符串必须满足两个条件：

• 原字符串中出现的字符，新字符串也必须包含。
• 新字符串中所有的字符均不相同。
• 新字符串的字典序是满足上面两个条件的最小的字符串。

输入描述:

仅一行，有一个只含有可打印字符的字符串 s。 |s|≤105

输入

bab

输出

ab

输入

baca

输出

bac

删除若干字符，新字符串中仅包含一个原字符串中字母，并且字典序要最小。

关注到底需要记录什么，只需要记最后一次出现的位置即可。前面的可删去。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<char,int> m,mm;//一个用于记录最后位置 一个用于标记是否出现了
stack<char> ss;//用于放置新字符
int main()
{string s;cin>>s;for(int i=0; s[i]; i++)m[s[i]]=i;for(int i=0; s[i]; i++){if(mm[s[i]]==0){while(!ss.empty()&&p()>s[i]&&p()]>i)//一定记得判空{p()]=0;ss.pop();}ss.push(s[i]);mm[s[i]]=1;}}s.clear();while(!ss.empty())//输出字符串{s+&#p();ss.pop();}reverse(s.begin(),s.end());//字符串逆转直接用reversecout<<s<<endl;return 0;
}