《技术》学考及选考相关问题请联系张博士13958083702(手机和微信同号) 问题 5880 --数字游戏

5880: 数字游戏★★★

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

题目描述

现有一个长度为n的正整数数组a,云卓和昕旸两位小朋友准备玩一个数字游戏。

在游戏开始前,云卓小童鞋先选择一个整数kk≥0),游戏进行k回合,依次编号为123,……,k。在第i回合,云卓必须从数组a中选择一个小于等于k-i+1的元素x,将其从数组a中移除。此时,如果数组非空,则昕旸可以任意选择数组中的一个元素,将该元素加上k-i+1。在游戏的第i个回合中,如果云卓不能从数组a中找到满足条件的元素xx<=k-i+1,则云卓小童鞋失败,昕旸小童鞋胜利;如果k回合游戏结束后,云卓小朋友仍然没有失败,则云卓小朋友获得胜利。

你的任务是:在两位小朋友都采用最优策略的前提下,如果云卓小朋友想要获得游戏的最终的胜利,云卓能够选择的k值最大是多少?

特别提醒:一回合是指云卓和昕旸各自完成他们的操作。

输入

第一行只有一个整数t(1≤t≤100):测试用例的数量。

接下来共2t行,每个测试用例2行:

第一行一个整数n2≤n≤100):数组a的长度。

      第二行共n个整数a1,a2,a3,……,an1≤ai≤n ):数组an个元素的值。

输出

t行,每个测试用例一行一个整数:云卓获胜的前提下,所能选取的k最大值;

样例输入
Copy
4
3
1 1 2
4
4 4 4 4
1
1
5
1 3 2 1 1
样例输出
Copy
2
0
1
3

提示

来源

 

[提交][状态]

如有问题,请咨询客服
浙ICP备20001167号