← 返回题目列表

Codeforces · 2060/C

C. 数学游戏

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

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\cdot 10^5, 1 \leq k \leq 2\cdot n$$$, $$$n$$$ 是偶数)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$x_1,x_2,\ldots,x_n$$$ ($$$1 \leq x_i \leq n$$$) — 黑板上的整数。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 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$$$。

请注意,这只是出于演示目的游戏如何进行的示例。这可能不是爱丽丝或鲍勃的最佳策略。