CF1987D World is Mine

题目描述

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

Alice 和 Bob 轮流吃蛋糕，Alice 先手：

• 在她的回合，Alice 可以选择并吃掉任意一个剩下的蛋糕，前提是该蛋糕的美味值严格大于她之前吃过的所有蛋糕中的最大美味值。注意，在第一回合，她可以选择任意一个蛋糕。
• 在他的回合，Bob 可以选择并吃掉任意一个剩下的蛋糕。

当当前玩家无法吃到合适的蛋糕时，游戏结束。设 $x$ 为 Alice 吃掉的蛋糕数量。Alice 希望最大化 $x$，而 Bob 希望最小化 $x$。

如果双方都采取最优策略，求 Alice 最终能吃到多少个蛋糕。

输入格式

每组测试数据包含多个测试用例。输入的第一行包含一个整数 $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$。

输出格式

对于每个测试用例，输出一个整数，表示在双方都采取最优策略的情况下，Alice 能吃到的蛋糕数量。

输入输出样例 #1

输入 #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$ 的蛋糕，她无法再进行操作，游戏结束。

由 ChatGPT 4.1 翻译