[C++知识库]Codeforces Round #767 (Div. 2) C. Meximum Array

要想让b数组尽可能的大，我们每次要先取最大的mex，并且贪心地让取得mex的数的个数尽可能地少，比如：0 2 1 0 1，最大的mex是3，那么要贪心的取最少的数即0 2 1 而不是 0 2 1 0 1
首先预处理数组mex[i]，即i~n的mex值，因为计算mex的值会不断移除数组前边的数，为了不让已经移除的数影响mex值，所以计算后缀的最大的mex值
我们每次要放入b数组的数肯定是最大的mex，那么从前向后遍历a数组，设当前遍历的位置是i，如果从i到j这一段的mex的值等于最大的mex的值，那么就将这个mex值放入b数组

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

const int N = 200010;

int t, n, a[N], mex[N];
vector<int> res;

int main()
{
    cin >> t;
    while(t --)
    {
        res.clear();
        cin >> n;
        for(int i = 1; i <= n; i ++) 
        {
            cin >> a[i];
        }
        
        map<int,int> cnt;
        for(int i = n, j = 0; i >= 1; i--)
		{
			cnt[a[i]]++;
			while (cnt[j]) j++;
			mex[i]=j;
		}
	
	    for(int i = 1; i <= n;)
	    {
	        map<int,int> mp;
	        int j = i, cur_mex = 0;
	        mp[a[j]] ++;
	        while(mp[cur_mex]) cur_mex ++;
	        while(cur_mex != mex[i])
	        {
	            mp[a[++j]] ++;
	            while(mp[cur_mex]) cur_mex ++;
	        }
	        res.push_back(cur_mex);
	        i = j + 1;
	    }
		cout << res.size() << endl;
		for(auto& x : res) cout << x << ' ';
		cout << endl;
    }
}