Codeforces Round #767 (Div. 2) - C

题目翻译

Mihai刚刚了解了MEX的概念，因为他非常喜欢它，所以他决定立即使用它。

给定 n 非负整数的数组a，Mihai希望创建一个新的数组b，其形式如下：

虽然 a 不是空的：

• 选择一个整数 k（1≤k≤ |a| ）。
• 将数组a的前 k 个数的MEX附加到数组b的末尾，并将它们从数组a中删除，从而移动a中其余数的位置。

但是，由于Mihai和MEX概念一样喜欢大数组，他希望新的数组b在词典编纂上是最大的。所以，Mihai让你告诉他，通过优化构建数组可以创建的最大数组b是多少。

如果在第一个位置 x 和 y 不同 xi>yi，或者如果 | x |>| y |，并且 y 是 x 的前缀（其中| x |表示数组x的大小），那么数组x在词典学上大于数组y。

一组非负整数的MEX是最小的非负整数，因此它不在该集合中。例如，MEX（{1,2,3}）=0和MEX（{0,1,2,4,5}）=3。

输入

输入的第一行包含一个整数t（1≤t≤100）-测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数n（1≤N≤2⋅1e5）-数组中的元素数a。

每个测试用例的第二行包含 n 个非负整数a1，…，an（0≤ai≤n） ，其中ai是数组a中的第二个整数。

保证所有测试用例的n之和不超过2⋅1e5

输出

对于每个测试用例，print m—— Mihai可以创建的最大数组b长度，后面是表示数组b元素的m整数。

样例

输入

6
5
1 0 2 0 3
8
2 2 3 4 0 1 2 0
1
1
5
0 1 2 3 4
4
0 1 1 0
10
0 0 2 1 1 1 0 0 1 1

输出

1
4 
2
5 1 
1
0 
1
5 
2
2 2 
4
3 2 2 0 
 

解题思路

我们先一遍循环找到所有数的位置，然后在取值区间内找到最小的未出现的数，存储结果后再找他MEX的最右端，更新区间 l 和 r 信息之后按题目要求删除，在进行下一次操作。

代码示例

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

int t,n;
int a[250000];
int b[250000];
int l=1,r=0;
int cnt;
queue<int> q[250000];

int main(){
	cin>>t;
	while(t--){
		cin>>n;
		cnt=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			q[a[i]].push(i);
		}
		l=1,r=0;
		while(l<=n){
			r=l;
			for(int i=0;i<=n+1;i++){
				if(q[i].empty()){
					b[++cnt]=i;
					break;
				}
				r=max(r,q[i].front());
			}
			for(int i=l;i<=r;i++) q[a[i]].pop();
			l=r+1;
		}
		cout<<cnt<<endl;
		for(int i=1;i<=cnt;i++) cout<<b[i]<<" ";
		cout<<endl;
		
	}
}