问题 5623 --字典序最大的MinX数组

5623: 字典序最大的MinX数组★★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 16  解决: 9
[提交][状态][命题人:]

题目描述

张博士刚刚了解了MinX的概念,被MinX深深吸引,所以张博士决定立即使用MinX构建一个特殊的数组。

MinX的定义如下:一个非负整数集合的MinX值为不在该集合中的最小非负整数。例如:MinX ({1,2,3}) = 0; MinX ({0,1,2,4,5}) = 3

现给定一个包含n个非负整数的数组a, 张博士想要创建一个新的数组b,其形式如下:

a不为空时:

1)选择一个整数k(1≤k≤|a||a|表示数组的长度,即数组中的元素个数)

2)将数组a的前k个整数的MinX值附加到数组b的末尾,并将前k个整数从数组a中删除。显然,|a|会同步减小。·

但是,由于张博士喜欢大数组和MinX概念一样多,所以张博士希望新数组b在字典结构上是最大的。所以,张博士让你告诉他,通过最优地构造数组可以创建的最大数组b是多少。

数组字典结构的大小关系定义如下:如果数组x和数组y的第一个元素值不同的位置为i(即前i-1个元素都相等)且有xi>yi,或者如果|x|>|y|yx的前缀(其中|x|表示数组x的大小),则数组x在字典结构上大于数组y

输入

第一行一个整数t1≤t≤100):测试用例数。

接下来共t个测试用例,每个测试用例共两行输入:

第一行一个整数n1≤n≤2*105):数组a的长度。

第二行共n个非负整数:数组an个元素a1,a2,……,ai,……,an的值(0≤ai≤n )

输出

输出共两行:

第一行一个整数m:数组b的长度。

     第二行共m个整数(两个整数之间用一个空格分开):数组b中的元素。
样例输入
Copy
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
样例输出
Copy
1
4 
2
5 1 
1
0 
1
5 
2
2 2 
4
3 2 2 0

提示

在第一个测试用例中,通过选择k=5获得字典结构上最大的数组b,从而得到整个数组a的MinX数组。它是字典上最大的,因为以小于4开头的数组在字典上更小,而选择k<5将导致以小于4开头的数组。

      在第二个测试用例中,有两种方法可以获得最大数组:首先选择k=6,然后k=2,或者首先选择k=7,然后k=1。

来源

 

[提交][状态]