Meximum Array

Meximum Array

Codeforces Round #767 (Div. 2)，C题Meximum Array
可以用双指针在O(n)的复杂度内求解。
先用num数组存一下每个数字出现的次数，然后跑一遍num，贪心找到当前最大MEX。之后用双指针枚举a数组，删除数组中0-MEX-1的数字(一共有MEX个，可以重复删，但是每个数字都要删到），期间可以开个vis数组，并用cnt统计一下删除的数字个数。注意到如果有数字删完了一定要及时更新MEX。
最后注意一下数组清空问题，一定不要在双指针内直接vector< int >vis(n+1)，这样写，会被卡成O(n^2)，然后TLE！请用for清空数组。

具体代码如下:

#include 
using namespace std;
const int N=2e5+5;
int n,a[N],num[N];
bool vis[N];
void solve()
{
	int mex=0;
	vectorans;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) num[a[i]]++;
	while(num[mex]>0) mex++;
	for(int i=1;i<=n;i++)
	{
		int now=mex,cnt=0;
		ans.push_back(now);
		for(int j=i;j<=n;j++)
		{
			num[a[j]]--;
			if(num[a[j]]==0&&a[j]T;
	while(T--) solve();
	return 0;
}