Codeforces Round#767(Div.2) C. Meximum Array

Codeforces Round#767(Div.2) C. Meximum Array 题意

对于一个数列，输出字典序最大的MEX数串。

题解

由于需要字典序最大，其实思路就很明显了，我们需要将越大的数放在前面，那我们只要计数排序下一个数字是否在数组中存在，然后在用一个set来维护当前已经在数组中的数即可。

#include
using namespace std;
typedef unsigned long long ll;
const int N = 2e5 + 10;
int  cnt[N],a[N],st[105];
void solve()
{
	int n;
	cin >> n;
	for (int i = 0; i <= n; i++)cnt[i] = 0;
	for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); cnt[a[i]]++; }
	vector res;
	int temp = -1;
	ll sum=0;
	sets;
	for (int i = 1; i <= n; i++)
	{   
		if (cnt[temp + 1])
		{
			cnt[a[i]]--;
			if (a[i] == temp+1)temp++;
		   s.insert(a[i]);
		   int flag = 0;
		   while (1)
		   {
			   if (s.count(temp) )temp++, flag = 1;
			   else break;
		   }
		   if (flag)temp--;
		}
		if(!cnt[temp+1])
		{
			res.push_back(temp+1);
			temp = - 1;
			s.clear();
		}
		//cout << temp<<" ";
	}
	cout << res.size()<> t;
	while (t--)solve();
}