https://codeforces.com/contest/797/problem/C
题目大意
给出小写字母构成的字符串 $A \ (|A| \le 10^5)$，和空串 $B, C$。每次操作可以做以下操作之一：
- 将 $A$ 开头的字符移动到 $B$ 结尾。
- 将 $B$ 结尾的字符移动到 $C$ 结尾
重复操作直到 $A, B$ 为空。问能得到字典序最小的 $C$ 是什么。
简要题解
其实这里 $A$ 相当于一个即将入栈的序列。$B$ 相当于一个栈。$C$ 是一个出栈序列。
可以想到，我们要把当前能放的尽可能小的字符放到最前。假设最小字符是 $a$ 则一定是把所有 $a$ 先放完，这件事显然是可以做到的，我们只有把 $a$ 入栈时，直接把其弹出。这个过程不可避免的要把一些更大的字符进栈，显然一个字符尽量不进栈是更好的，因为它可以之后随时选择进栈，因此处理完最后一个 $a$ 之后不会先把剩余字符进栈。考虑当前要处理某字母 $x$，如果栈头是一个 $x$，这里我们优先弹出盏头会更好（一方面如果先处理没入栈的 $x$ 则有可能之后进来一些更大字符将栈头堵住，另一方面，之前栈里可能有比 $x$ 更小的元素，先处理栈的话可能会将这些元素先弹出得到更小的字典序）。至此我们得到了完整的算法。
复杂度
$T$：$O(n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
string s; cin >> s;
int n = s.length();
vector<int> lst(26, -1);
for (int i = 0; i < n; i++) {
lst[s[i] - 'a'] = i;
}
stack<char> st;
string ans;
int cur = 0;
for (int i = 0; i < 26; i++) {
char c = i + 'a';
while (!st.empty() && st.top() <= c) {
ans += st.top(); st.pop();
}
while (cur <= lst[i]) {
if (s[cur] == c) {
ans += c;
} else {
st.push(s[cur]);
}
cur++;
}
}
cout << ans << '\n';
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: E. Array Queries - Educational Codeforces Round 19