Educational Codeforces Round 156 (Rated for Div. 2)

C. Decreasing String

分析：暴力做法是很容易想到的，但时间复杂度为O(n2)

这是我打cf以来看到的最好的题解。

#include
#include
#include
#include
#include
#include
#include
#include
#include 
#include
#include
#include
#include
#include
#include 
#include
#include 
 
#define inf 0x3f3f3f3f
#define int long long
const int N =2e5 + 10;
//#include 
typedef long long ll;
#include
using namespace std;
 
//long long MAX(long long a, long long b) { return a < b ? b : a; }
 
 
signed main() {
	int T; cin >> T;
	while (T--) {
		string s; cin >> s;
		int pos; cin >> pos;
		pos--;//处理完可以直接s[pos]这样访问
		
		int curLen = s.size();
		bool f = pos < curLen;//如果为true，就不用再删了
		s.push_back('a' - 1);
		vector<char> st;
		for (auto c : s) {
			if (!st.size()) {
				st.push_back(c);
				continue;
			}
			
			
 
			while (!f && c < st.back()) {
				st.pop_back();//每删一次就代表操作了一次，pos要减去当前长度
				pos -= curLen;
				curLen--;
				if (pos < curLen) f = true;
			}
			st.push_back(c);
		}
		cout << st[pos];
	}
 
	return 0;
}