CF1946A.Median of an Array

给定一个长度为 $n$ 的整数数组 $a$。

一个数组 $q_1, q_2, \ldots, q_k$ 的中位数定义为排序后数组 $p$ 的第 $\lceil \frac{k}{2} \rceil$ 个数，即 $p_{\lceil \frac{k}{2} \rceil}$。例如，数组 $[9, 5, 1, 2, 6]$ 的中位数是 $5$，因为排序后为 $[1, 2, 5, 6, 9]$，第 $\lceil \frac{5}{2} \rceil = 3$ 个数是 $5$；数组 $[9, 2, 8, 3]$ 的中位数是 $3$，因为排序后为 $[2, 3, 8, 9]$，第 $\lceil \frac{4}{2} \rceil = 2$ 个数是 $3$。

你可以进行若干次操作，每次选择一个整数 $i$（$1 \le i \le n$），将 $a_i$ 增加 $1$。

你的任务是求出最少需要多少次操作，才能使数组的中位数增加。

注意，数组 $a$ 中的数不一定各不相同。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示数组 $a$。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示最少需要多少次操作才能使数组的中位数增加。

在第一个测试用例中，你可以对第一个数进行一次操作，得到数组 $[3, 2, 8]$，此时中位数为 $3$，因为排序后为 $[2, 3, 8]$，第 $\lceil \frac{3}{2} \rceil = 2$ 个数是 $3$。原数组 $[2, 2, 8]$ 的中位数为 $2$，排序后为 $[2, 2, 8]$，第 $\lceil \frac{3}{2} \rceil = 2$ 个数是 $2$。因此，中位数在一次操作后增加了（$3 > 2$）。

在第四个测试用例中，你可以对第 $1, 2, 3$ 个数各进行一次操作，得到数组 $[6, 6, 6, 4, 5]$，此时中位数为 $6$，排序后为 $[4, 5, 6, 6, 6]$，第 $\lceil \frac{5}{2} \rceil = 3$ 个数是 $6$。原数组 $[5, 5, 5, 4, 5]$ 的中位数为 $5$，排序后为 $[4, 5, 5, 5, 5]$，第 $\lceil \frac{5}{2} \rceil = 3$ 个数是 $5$。因此，中位数在三次操作后增加了（$6 > 5$），且这是最少的操作次数。

在第五个测试用例中，你可以对第 $1, 3$ 个数各进行一次操作，得到数组 $[3, 1, 3, 3, 1, 4]$，此时中位数为 $3$，排序后为 $[1, 1, 3, 3, 3, 4]$，第 $\lceil \frac{6}{2} \rceil = 3$ 个数是 $3$。原数组 $[2, 1, 2, 3, 1, 4]$ 的中位数为 $2$，排序后为 $[1, 1, 2, 2, 3, 4]$，第 $\lceil \frac{6}{2} \rceil = 3$ 个数是 $2$。因此，中位数在两次操作后增加了（$3 > 2$），且这是最少的操作次数。

由 ChatGPT 4.1 翻译