【数据结构】Decreasing String—CF1886C

Decreasing String—CF1886C

代码我现在还不是很理解，群友说是单调栈。

$Code$

#include <bits/stdc++.h>
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using PII = pair<int, int>;
using i128 = __int128;
const int N = 2e5 + 10;int n;void solve() {string s; cin >> s;n = sz(s);s.insert(s.begin(), ' ');int pos; cin >> pos;int cut = 0; // 还剩几个字符需要删除int idx = -1; // 在t字符串中的下标for (int i = n; i >= 1; i --) {if (pos > i) {pos -= i;} else {cut = n - i;idx = pos;break;}}string t;for (int i = 1; i <= n; i ++) {while (not t.empty() && cut && s[i] < t.back()) {t.pop_back();cut --;}t += s[i];}cout << t[idx - 1];
}signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T = 1;cin >> T; cin.get();while (T --) solve();return 0;
}