每天一道英文题,ICPC不自闭(28)

每天一道英文题,ICPC不自闭(28),第1张

每天一道英文题,ICPC不自闭(28)

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

2
5 1 
1

1

2
2 2 
4
3 2 2 0 
 

解题思路

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

代码示例
#include
#include
#include
#include
#include
#include
using namespace std;

int t,n;
int a[250000];
int b[250000];
int l=1,r=0;
int cnt;
queue 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<					
										


					

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5718765.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-18
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存