← 返回题目列表

Codeforces · 1987/D

D. 世界是我的

中文机器翻译题面 查看原题

Alice 和 Bob 正在玩游戏。最初,有 $$$n$$$ 个蛋糕,第 $$$i$$$ 个蛋糕的美味值为 $$$a_i$$$。

Alice 和 Bob 轮流吃它们,Alice 首先开始:

- 轮到爱丽丝选择并吃掉任何剩余的蛋糕,其味道严格高于她之前吃过的任何蛋糕的最大味道。请注意,在第一回合,她可以选择任何蛋糕。
- 轮到鲍勃选择剩余的蛋糕并吃掉它。

当前玩家吃不到合适的蛋糕时游戏结束。令 $$$x$$$ 为爱丽丝吃的蛋糕数量。然后,Alice 想要最大化 $$$x$$$,而 Bob 想要最小化 $$$x$$$。

找出如果两个玩家都发挥最佳状态,爱丽丝会吃多少个蛋糕。

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) - 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$) — 蛋糕的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — 蛋糕的美味值。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。

输出

对于每个测试用例,输出一个整数 - 如果两个玩家都发挥最佳状态,爱丽丝将吃的蛋糕数量。

示例

输入 #1

9
4
1 4 2 3
3
1 1 1
5
1 4 2 3 4
4
3 4 1 4
1
1
8
4 3 2 5 6 8 3 4
7
6 1 1 3 5 3 1
11
6 11 6 8 7 5 3 11 2 3 5
17
2 6 5 3 9 1 6 2 5 6 3 2 3 9 6 1 6

输出 #1

2
1
3
2
1
3
2
4
4

注意

在第一个测试用例中,一个可能的轮次顺序是:

1. Alice 吃了一块美味值为 $$$1$$$ 的蛋糕。剩下的蛋糕是$$$[4,2,3]$$$。
2. Bob 吃了一块美味值为 $$$2$$$ 的蛋糕。剩下的蛋糕是$$$[4, 3]$$$。
3. Alice 吃了一块味道为 $$$3$$$ 的蛋糕。剩下的蛋糕是$$$[4]$$$。
4. Bob 吃了一块美味值为 $$$4$$$ 的蛋糕。剩下的蛋糕是$$$[]$$$。
5. 由于没有剩下蛋糕,游戏结束。

在第二个测试用例中,一种可能的轮流顺序是:

1. Alice 吃了一块美味值为 $$$1$$$ 的蛋糕。剩下的蛋糕是$$$[1, 1]$$$。
2. Bob 吃了一块美味值为 $$$1$$$ 的蛋糕。剩下的蛋糕是$$$[1]$$$。
3. 由于 Alice 已经吃了一块美味值为 $$$1$$$ 的蛋糕,她无法进行回合,因此游戏结束。