A16573 | $Game of Mathletes$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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 则试图最大化分数。假设双方均采取最优策略，游戏结束时的分数是多少？

第一行包含一个整数 $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$。

对于每个测试用例，输出双方均采取最优策略时的最终分数。

输入 #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

C++ 编辑器

输入

输出