题目难度: 1700rating
题目类型：string+贪心+STL
题目思路：
由于题目要求的最终结果是字典序最小的那个字符串，那么我们从贪心的从’a’开始查找字符串里是否存在，如果存在，就先把后面的所有的该字符放在答案字符串u中(u可以用queue来表示)，而字符串t可以用stack来表示。
中间的字符串都加入到stack中，当一个字符全加入后，继续从小到大的查找剩余字符串中还剩的字符，并且与栈顶元素进行比较，如果小于栈顶元素，需要先输出栈顶元素。
中间的细节比较多，详细看代码。
我用的map来维护剩余的字符数量。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <stack>
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb std::ios::sync_with_stdio(false)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define gg(x) getInt(&x)
using namespace std;
typedef long long ll;
inline void getInt(int* p);
const int maxn=;
/*** TEMPLATE CODE STARTS HERE ***/
char s[maxn];
int n;
map<char ,int > m;
int main()
{
scanf("%s",s);
n=strlen(s);
rep(i,,n)
{
int x=m[(s[i])];
m[(s[i])] =x+;
}
stack<char> st;
queue<char> q;
while(!q.empty())
{
q.pop();
}
while(!st.empty())
{
st.pop();
}
char x='a'-;
int index=;
while(q.size()!=n)
{
char i;
for( i='a';i<='z';i++)
{
if(m.count(i)!=&&m[i]!=)
{
x=i; break;
}
}
if(i=='z'+)
{
if(!st.empty())
x=st.top();
}
if(!st.empty()&&st.top()<x)
{
x=st.top();
} while(!st.empty()&&st.top()==x)
{
st.pop();
q.push(x);
if(!st.empty()&&st.top()<x)
{
x=st.top();
}
}
if(m.count(x)==||m[x]==)
continue;
int num=m[x];
m.erase(x);
for(int j=index;j<n;j++)
{
if(s[j]==x)
{
q.push(x);
num--;
}else
{
st.push(s[j]);
m[s[j]]=m[s[j]]-;
}
if(!num)
{
index=j+;
break;
}
} }
while(!q.empty())
{
printf("%c",q.front());
q.pop();
}
return ;
} inline void getInt(int* p) {
char ch;
do {
ch = getchar();
} while (ch == ' ' || ch == '\n');
if (ch == '-') {
*p = -(getchar() - '');
while ((ch = getchar()) >= '' && ch <= '') {
*p = *p * - ch + '';
}
}
else {
*p = ch - '';
while ((ch = getchar()) >= '' && ch <= '') {
*p = *p * + ch - '';
}
}
}