← 返回题目列表

Codeforces · 1943/A

A. 墨西哥游戏 1

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

Alice 和 Bob 在大小为 $$$n$$$ 的数组 $$$a$$$ 上玩另一个游戏。 Alice 从一个空数组 $$$c$$$ 开始。两名玩家轮流玩,爱丽丝先开始。

轮到 Alice 时,她从 $$$a$$$ 中选择一个元素,将该元素附加到 $$$c$$$,然后从 $$$a$$$ 中删除它。

轮到 Bob 时,他从 $$$a$$$ 中选择一个元素,然后从 $$$a$$$ 中删除它。

当数组 $$$a$$$ 为空时游戏结束。游戏得分定义为 $$$c$$$ 的 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 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < n$$$)。

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

输出

对于每个测试用例,如果两个玩家都发挥最佳,则找到游戏的得分。

示例

输入 #1

3
4
0 0 1 1
4
0 1 2 3
2
1 1

输出 #1

2
1
0

注意

在第一个测试用例中,得分为 $$$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$$$。请注意,这是一个示例游戏,并不一定代表双方玩家的最佳策略。