[数据结构与算法]贪心+模拟

A. Meximum Array
code：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define eps 1e-6
using namespace std;
const int maxn = 2e6 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
int a[maxn];
int cnt[maxn];
void work()
{
	cin >> n;
	for(int i = 0; i <= n; ++i) cnt[a[i]] = 0;
	for(int i = 1; i <= n; ++i) cin >> a[i], cnt[a[i]] += 1;
	int l = 1;
	vector <int> v;
	while(l <= n)
	{
		int mex = 0;
		while(cnt[mex]) mex++;
		vector <bool> vis(mex + 1);
		int c = 0;
		while(l <= n)
		{
			if(a[l] < mex && !vis[a[l]]){
				vis[a[l]] = 1;
				c += 1;
			}
			cnt[a[l]]--;
			++l;
			if(c == mex) break;
		}
		v.push_back(mex);
	}
	cout << v.size() << endl;
	for(auto x : v) cout << x << " ";cout << endl;
}

int main()
{
	ios::sync_with_stdio(0);
	int TT;cin>>TT;while(TT--)
	work();
	return 0;
}

B - Reserve or Reverse
code：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define eps 1e-6
using namespace std;
const int maxn = 2e6 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
vector <int> v[26];
string s;

void work()
{
	cin >> n >> s;
	for(int i = 0; i < s.size(); ++i)
		v[s[i]-'a'].push_back(i);
	int l = 0, r = n - 1;
	while(l < r)
	{
		int p = 0;
		while(p < 26)
		{
			while(!v[p].empty() && v[p].back() > r) v[p].pop_back();
			if(v[p].empty() || v[p].back() < l) ++p;
			else break;
		}
		if(s[l] - 'a' == p){
			++l;continue;
		}
		r = v[p].back();
		swap(s[l], s[r]);
		++l;
		--r;
	}
	cout << s;
}

int main()
{
	ios::sync_with_stdio(0);
//	int TT;cin>>TT;while(TT--)
	work();
	return 0;
}