CF1943A.MEX Game 1

Alice 和 Bob 又在一个长度为 $n$ 的数组 $a$ 上玩游戏。Alice 从一个空数组 $c$ 开始。两位玩家轮流操作，Alice 先手。

在 Alice 的回合，她从 $a$ 中选择一个元素，将其添加到 $c$ 的末尾，并从 $a$ 中删除该元素。

在 Bob 的回合，他从 $a$ 中选择一个元素，并从 $a$ 中删除该元素。

当数组 $a$ 为空时，游戏结束。游戏的得分定义为数组 $c$ 的 $\operatorname{MEX}^\dagger$。Alice 希望最大化得分，而 Bob 希望最小化得分。若双方都采取最优策略，求游戏的最终得分。

$\dagger$ 数组的 $\operatorname{MEX}$（最小未出现的非负整数）定义为：在该数组中没有出现的最小非负整数。例如：

• $[2,2,1]$ 的 MEX 是 $0$，因为 $0$ 没有出现在数组中。
• $[3,1,0,1]$ 的 MEX 是 $2$，因为 $0$ 和 $1$ 出现在数组中，但 $2$ 没有。
• $[0,3,1,2]$ 的 MEX 是 $4$，因为 $0$、$1$、$2$ 和 $3$ 都出现了，但 $4$ 没有。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 2 \times 10^4$），表示测试用例的数量。接下来是每组测试用例的描述。

每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i < n$）。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每组测试用例，若双方都采取最优策略，输出游戏的最终得分。

在第一个测试用例中，一种得分为 $2$ 的可能游戏过程如下：

1. Alice 选择元素 $1$。此时 $a=[0,0,1]$，$c=[1]$。
2. Bob 选择元素 $0$。此时 $a=[0,1]$，$c=[1]$。
3. Alice 选择元素 $0$。此时 $a=[1]$，$c=[1,0]$。
4. Bob 选择元素 $1$。此时 $a=[\,]$，$c=[1,0]$。

最终，$c=[1,0]$，其 MEX 为 $2$。注意，这只是一个示例过程，并不一定代表双方的最优策略。

由 ChatGPT 4.1 翻译