CF1956B Nene and the Card Game

你和 Nene 正在玩一款纸牌游戏。游戏使用一副包含 $2n$ 张牌的牌堆，每张牌上写有一个从 $1$ 到 $n$ 的整数，并且每个整数 $1$ 到 $n$ 恰好各出现 $2$ 次。此外，桌面上有一个区域用于放置打出的牌（初始时桌面为空）。 游戏开始时，这 $2n$ 张牌被分配给你和 Nene，每人各获得 $n$ 张牌。 接下来，你和 Nene 轮流进行 $2n$ 个回合，也就是说每人各进行 $n$ 次操作，由你先手。每一回合： - 当前玩家从自己手中选择一张牌，假设牌上的数字为 $x$。 - 如果桌面上已经有一张数字为 $x$ 的牌，则当前玩家获得 $1$ 分，否则不得分。然后，他将这张数字为 $x$ 的牌放到桌面上。 注意，所有回合都是公开进行的：每位玩家在任何时刻都能看到桌面上的所有牌。 Nene 非常聪明，她总是以最优策略选择出牌，以使自己在游戏结束（$2n$ 回合后）获得的分数最大。如果有多种最优选择，她会选择能让你最终得分最少的那种。 更正式地说，Nene 总是优先最大化自己的最终得分，其次最小化你的最终得分。 假设牌已经分配完毕，你手中的牌上的数字为 $a_1, a_2, \ldots, a_n$。请问如果你也采取最优策略，你最多能获得多少分？

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示你和 Nene 各自手中的牌数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示你手中每张牌上的数字。保证每个整数 $1$ 到 $n$ 在序列 $a_1, a_2, \ldots, a_n$ 中最多出现 $2$ 次。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示你在采取最优策略时最多能获得的分数。

在第一个测试用例中，你手中的牌上的数字为 $1$、$1$、$2$ 和 $3$。Nene 手中的牌上的数字为 $2$、$3$、$4$ 和 $4$。游戏过程可能如下： 1. 你选择一张数字为 $1$ 的牌并放到桌面上。 2. Nene 选择一张数字为 $4$ 的牌并放到桌面上。 3. 你选择另一张数字为 $1$ 的牌，获得 $1$ 分，并将其放到桌面上。 4. Nene 选择另一张数字为 $4$ 的牌，获得 $1$ 分，并将其放到桌面上。 5. 你选择数字为 $2$ 的牌并放到桌面上。 6. Nene 选择数字为 $2$ 的牌，获得 $1$ 分，并将其放到桌面上。 7. 你选择数字为 $3$ 的牌并放到桌面上。 8. Nene 选择数字为 $3$ 的牌，获得 $1$ 分，并将其放到桌面上。 最终，你获得 $1$ 分，Nene 获得 $3$ 分。可以证明，如果 Nene 采取最优策略，你无法获得超过 $1$ 分，因此答案为 $1$。 在第二个测试用例中，如果双方都采取最优策略，你可以获得 $2$ 分，Nene 获得 $6$ 分。 由 ChatGPT 4.1 翻译