CF2060C Game of Mathletes

题目描述

数学家的游戏

Alice和Bob正在玩一个游戏 这里有$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和Bob都十分睿智并采用了最优策略，试求游戏结束后用于计分的整数是多少.

输入格式

输入的第一行包含了一个正整数 $t$ ( $1 \leq t \leq 10^4$ ) — 也就是测试样例的次数

每个测试样例的第1行包含了两个正整数 $n$ 和 $k$ ( $ 2 \leq n \leq 2\cdot 10^5, 1 \leq k \leq 2\cdot n $ , $n$ 是偶数).

每个测试样例的第2行包含了$n$个正整数 $x_1,x_2,\ldots,x_n$ ( $1 \leq x_i \leq n$ ) — 也就是黑板上写的整数

出题人保证 $n$ 的在每个测试样例总和不会超过 $2\cdot 10^5$ .

输出格式

对于每个测试点，请输出Alice和Bob同时做出最佳决策的结果

输入输出样例 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

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 的最佳策略。