CF1506G 题解
liangbowen
2022-08-09 16:16:44
## 前言
[题目传送门！](https://www.luogu.com.cn/problem/CF1506G)
[更好的阅读体验？](https://liangbowen.blog.luogu.org/solution-cf1506g)
校内考试题目。写一篇题解。
## 思路
首先记录每个字符出现了多少次，然后创建**单调栈**。
看当前字符是否入栈，如果没有入栈，就不停 `pop()`，直到：
+ 栈空了。
+ 栈顶字典序大于当前字符。
+ 栈顶元素已经被删掉了（因为栈外面用 `cnt[i]` 记录了每个数的次数）。
满足单调栈要求后，压入当前字符。
不管是不是将当前字符压入栈了，都要将**对应计数器减一**。
最后，整个栈**从下往上**就是答案了。
如果使用 STL 的 `stack`，需要反着输出，这一点自己模拟一下栈的操作，就能理解了。
## 完整代码
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
void fastio()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
}
const int N = 30;
int cnt[N];
bool instk[N];
void solve()
{
memset(cnt, 0, sizeof(cnt)); //多测不清空，爆零两行泪！！！
memset(instk, false, sizeof(instk));
string s;
cin >> s;
int len = s.length();
for (int i = 0; i < len; i++) cnt[s[i] - 'a']++;
stack <int> stk; //单调栈
for (int i = 0; i < len; i++)
{
int x = s[i] - 'a';
if (!instk[x])
{
while (!stk.empty() && cnt[stk.top()] && x > stk.top()) instk[stk.top()] = false, stk.pop();
stk.push(x), instk[x] = true; //没进栈就进栈
}
cnt[x]--; //删除掉一个
}
string ans = "";
while (!stk.empty()) ans += (stk.top() + 'a'), stk.pop();
reverse(ans.begin(), ans.end());
cout << ans << '\n';
}
int main()
{
fastio();
int T;
cin >> T;
while (T--) solve();
return 0;
}
```
希望能帮助到大家！