[R33B]中位数 - 代码源竞赛平台

时空限制

1S/512M

题目描述

apiadu 得到了一个数组 $A$ 和一个他最喜欢的数字 $s$。他希望通过向数组 $A$ 中插入一些整数，使得 $s$ 成为新数组的中位数。

apiadu 想知道，他最少需要插入多少个数字才能达成目标？

我们对中位数的定义如下：对于一个长度为 $m$ 的数组，将其从小到大排序后，中位数是位于第 $\lfloor\frac{(m + 1 )}{2}\rfloor$ 位置的数字。（位置从 $1$ 开始计数）

符号 $\lfloor x \rfloor$ 表示对 $x$ 下取整，即取不大于 $x$ 的最大整数。例如：$\lfloor 3.5 \rfloor = 3$，$\lfloor 4 \rfloor = 4$。

格式

输入格式

本题包含多组测试数据。

输入的第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据，第一行包含两个整数 $n$ 和 $s$，分别表示数组 $A$ 的初始大小和他最喜欢的数字。

第二行包含 $n$ 个整数 $A_1, A_2, \dots, A_n$，表示数组 $A$ 的数字。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示最少需要插入的数字数量。

样例

样例输入 #1

3
3 20
10 20 30
5 50
1 2 3 100 200
5 50
10 20 100 200 300

样例输出 #1

0
2
1

样例解释 #1

对于第一个样例，原数组为 $[10, 20, 30]$，大小为 $3$。排序后中位数在第 $\lfloor\frac{(3+1)}{2}\rfloor = \lfloor 2 \rfloor = 2$ 个位置，该位置的数字是 $20$，已经是 $s$ 了。所以不需要插入任何数字，答案为 $0$。

对于第二个样例，原数组为 $[1, 2, 3, 100, 200]$，大小为 $5$，$s=50$。可以插入一个 $50$ 和 一个 $100$ ，此时数组变为 $[1,2,3,50,100,100,200]$，满足条件。故最少需要插入 $2$ 个数字。

对于第三个样例，原数组为 $[10, 20, 100, 200, 300]$，大小为 $5$，$s=50$。插入一个 $50$ 后，数组变为 $[10, 20, 50, 100, 200, 300]$。中位数在第 $\lfloor\frac{(6+1)}{2}\rfloor = \lfloor 3.5 \rfloor = 3$ 个位置。排序后第 $3$ 个数字是 $50$，满足要求。故最少需要插入 $1$ 个数字。

数据规模

对于 $100\%$ 的数据，$1 \leq T \leq 10^4$，$1 \leq n \leq 10^5$，$\sum n \leq 2 \times 10^5$，$1 \leq s, A_i \leq 10^9$。