A16573. Game of Mathletes
编程题
普及-
知识点
题目描述
Alice 和 Bob 正在玩一个游戏。黑板上有 $n$ 个整数（$n$ 为偶数），记为 $x_1, x_2, \ldots, x_n$。给定一个整数 $k$ 和一个初始为 $0$ 的分数。游戏持续 $\frac{n}{2}$ 轮，每轮按以下顺序执行：
- Alice 从黑板上选择一个整数并擦除。记 Alice 选择的整数为 $a$。
- Bob 从黑板上选择一个整数并擦除。记 Bob 选择的整数为 $b$。
- 若 $a + b = k$，分数增加 $1$。
Alice 的目标是尽可能最小化分数，而 Bob 则试图最大化分数。假设双方均采取最优策略，游戏结束时的分数是多少？
- Alice 从黑板上选择一个整数并擦除。记 Alice 选择的整数为 $a$。
- Bob 从黑板上选择一个整数并擦除。记 Bob 选择的整数为 $b$。
- 若 $a + b = k$，分数增加 $1$。
Alice 的目标是尽可能最小化分数，而 Bob 则试图最大化分数。假设双方均采取最优策略，游戏结束时的分数是多少？
输入格式
第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——测试用例数量。
每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 2 \times 10^5$，$1 \leq k \leq 2 \times n$，$n$ 为偶数）。
每个测试用例的第二行包含 $n$ 个整数 $x_1, x_2, \ldots, x_n$（$1 \leq x_i \leq n$）——黑板上的整数。
保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。
每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 2 \times 10^5$，$1 \leq k \leq 2 \times n$，$n$ 为偶数）。
每个测试用例的第二行包含 $n$ 个整数 $x_1, x_2, \ldots, x_n$（$1 \leq x_i \leq n$）——黑板上的整数。
保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。
输出格式
对于每个测试用例，输出双方均采取最优策略时的最终分数。
输入输出样例
输入 #1
4 4 4 1 2 3 2 8 15 1 2 3 4 5 6 7 8 6 1 1 1 1 1 1 1 16 9 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3
输出 #1
2 1 0 4
说明/提示
第一个测试用例中，游戏可能的一种进行方式如下：
- Alice 选择 $1$，Bob 选择 $3$。因 $1 + 3 = 4$，分数增加。此时黑板上剩余的两个整数为 $2$ 和 $2$。
- Alice 和 Bob 均选择 $2$。因 $2 + 2 = 4$，分数再次增加。
- 游戏结束，黑板上已无整数。
第三个测试用例中，Alice 和 Bob 选择的整数之和不可能为 $1$，因此答案为 $0$。
注意以上示例仅为演示可能的游戏流程，未必代表 Alice 或 Bob 的最优策略。
- Alice 选择 $1$，Bob 选择 $3$。因 $1 + 3 = 4$，分数增加。此时黑板上剩余的两个整数为 $2$ 和 $2$。
- Alice 和 Bob 均选择 $2$。因 $2 + 2 = 4$，分数再次增加。
- 游戏结束，黑板上已无整数。
第三个测试用例中，Alice 和 Bob 选择的整数之和不可能为 $1$，因此答案为 $0$。
注意以上示例仅为演示可能的游戏流程，未必代表 Alice 或 Bob 的最优策略。