A. 数组的中位数 详细题解

题目核心理解

给定一个长度为 $n$ 的数组 $a$。 数组的中位数定义为：将数组非降序排序后，位于下标 $\lceil\frac{n}{2}\rceil$ 位置上的数。

每次操作可以选择任意一个元素并将其加 $1$。 目标：求出使数组中位数严格变大所需的最少操作次数。

---

核心思路

1. 关键性质

• 中位数只和排序后数组后半部分的数字有关。
• 要让中位数变大，只需要把原中位数位置及之后连续等于原中位数的数各加 $1$。
• 最优策略：只修改排序后从中位数位置开始、所有等于原中位数的数。

2. 计算规则

设排序后数组为 $a$。 中位数位置：

$$pos = \lceil\frac{n}{2}\rceil$$

原中位数 $x = a[pos]$。

找到最大的下标 $t$，使得 $a[t] = x$。 最少需要的操作次数为：

$$t - pos + 1$$

---

算法流程

1. 将数组从小到大排序。
2. 计算中位数位置 $pos = \lceil\frac{n}{2}\rceil$。
3. 从 $pos$ 向后遍历，找到最后一个等于 $a[pos]$ 的位置 $t$。
4. 答案即为从 $pos$ 到 $t$ 的数字个数。
5. 输出该数量。

---

公式与复杂度分析

核心公式：

$$pos = \left\lceil \frac{n}{2} \right\rceil$$ $$ans = \text{满足 } a_i = a[pos] \text{ 且 } i \ge pos \text{ 的元素个数} $$

复杂度

• 排序：$O(n\log n)$
• 遍历统计：$O(n)$
• 总时间复杂度：$O(n\log n)$

可轻松处理 $n\le 10^5$、所有测试用例 $\sum n\le 2\times10^5$ 的数据范围。