「05」排序应用 - 中位数

最小绝对偏差之和

一组数据到中位数的绝对距离之和是最小的。

如果有一组数 $x_1, x_2, \dots, x_n$，我们要找一个数 $a$，使得 $\sum_{i=1}^{n} |x_i - a|$ 最小，那么这个 $a$ 就是中位数。

证明

方法一：直观几何法（数轴移动法）

不妨假设 $x_1 \le x_2 \le \cdots \le x_n$。

1. 考虑两个点的情况： 设有 $x_1$ 和 $x_2$。
   • 如果 $a$ 在 $[x_1, x_2]$ 之间，距离之和 $|x_1 - a| + |x_2 - a|$ 恰好等于线段的长度 $x_2 - x_1$（常数）。
   • 如果 $a$ 在线段外面，距离之和一定会大于线段长度。
2. 推广到 $n$ 个点：我们可以“一对一对”地看。为了最小化距离总和，我们要同时满足：
   • $a$ 在最外层两个点 $(x_1, x_n)$ 之间；
   • $a$ 在次外层两个点 $(x_2, x_{n-1})$ 之间；
   • ……依此类推。

结论：如果 $n$ 是奇数，$a$ 必须落在最中间的那个点上，即中位数。如果 $n$ 是偶数，$a$ 落在中间两个数之间的任何位置（包括端点），距离之和都相等且最小。

从上面的讨论可知，最小值为 $(x_n - x_1) + (x_{n - 1} - x_2) + (x_{n - 2} - x_3) + \cdots$。

方法二：代数符号法（扰动法）

假设 $a$ 是当前的候选值。我们观察当 $a$ 向右移动一个微小的距离 $\Delta > 0$ 时，总距离 $S = \sum |x_i - a|$ 会如何变化。

• 设 $N_\text{left}$ 为 $a$ 左侧的数据点个数。对于这些点，$|x_i - a|$ 会增加 $\Delta$。
• 设 $N_\text{right}$ 为 $a$ 右侧的数据点个数。对于这些点，$|x_i - a|$ 会减少 $\Delta$。
• 总变化量 $\Delta S = (N_\text{left} - N_\text{right}) \cdot \Delta$。

推导结论：

• 如果 $N_\text{left} < N_\text{right}$（右边点多），那么 $\Delta S$ 为负，说明右移能减小总距离。
• 如果 $N_\text{left} > N_\text{right}$（左边点多），那么左移能减小总距离。
• 最小值点： 只有当 $N_\text{left}$ 尽可能等于 $N_\text{right}$ 时（即 $a$ 处于中位数位置），函数停止减小并达到最优。

相关题目

例1. 士兵站队问题

例2. 均分纸牌

均分纸牌

有 $m$ 个人排成一行，她们手中分别有 $C[1] \sim C[m]$ 张纸牌，在每一步操作中，可以让某个人把自己手中的一张牌交给他旁边的一个人，

我们通过一个具体的例子来说明本题的计算方法。假设有 $5$ 个人，他们手上的牌的数量分别是 $8, 1, 3, 11, 2$。

为了均分他们手中的牌，我们首先计算出总共有 $25$ 张牌，平均下来每个人 $5$ 张，那么第一个人将向右传递 $3$ 张牌，第二个人需要他的右边给他 $1$ 张牌，第三个人需要他的右边给他 $3$ 张牌，最后，第四个人需要向他的右边传递 $3$ 张牌。

如果用正数表示向右边的人传递牌，负数表示右边的人传递过来的牌，那么，前四个人传递牌的数量分别是 $3$、$-1$、$-3$、$3$。

按照上面的方法，足以解决本题，我们依次枚举每个人，若第 $i$ 个人手中的牌数量为 $a_i$，平均数 avg，则多了 $a_i - avg$ 的牌，那将这些牌给第 $i + 1$ 人，即 $a_{i + 1}$ 增加 $a_i - avg$。注意 $a_i - avg$ 可能为负数，这表示从 $a_{i + 1}$ 处拿了牌过来。另外，有可能在计算过充，某个 $a_{i + 1}$ 变为了负数，但也没关系，在实际操作中可以让 $i + 1$ 先从右边拿牌。

参考代码

#include <bits/stdc++.h>
using namespace std;

int n, A[105];
int main() {
   cin >> n;
  int avg = 0;
  for (int i = 1; i <= n; i++) cin >> A[i], avg += A[i];
  avg /= n;

  int sum = 0;
  for (int i = 1; i < n; i++) {
     sum += (A[i] - avg != 0);
    A[i + 1] += A[i] - avg;
  }  
  cout << sum << endl;
}

后面的分析是为下一题做准备，

设平均牌数数为 $avg$，传递牌之前，每个人手中牌的数量的前缀和为 $S[i]$，那么，到第 $i$ 个人的时候，若 $S[i] \ge i \times \text{avg}$，那么，那么，第 $i$ 个人将给与第 $i + 1$ 个人 $S[i] - i\times \text{avg}$ 张牌，否则，第 $i$ 个人将从第 $i + 1$ 个人手中获取 $|S[i] - i \times \text{avg}|$ 的牌。所以，总共移动的牌的数量即为 $\displaystyle \sum_{i = 1}^n |S[i] - i\times \text{avg}|$。

如果我们在传递之前，让每个人手中的牌都减少相同的量，这不会影响最终的结果，因此，让每个人手中的牌均减少 $avg$，上面的结果将变为 $\displaystyle \sum_{i = 1}^n |S[i]|$。(这里的 $S[i]$ 是指减去 avg 以后新的 $S[i]$，与上面的 $S[i]$ 不相等。)

例3. 糖果传递

糖果传递

有 $n$ 个小朋友坐成一圈，每人有 $a_i$ 颗糖果。每人只能给左右两人传递糖果。每人每次传递一颗糖果的代价为 $1$ 。求使所有人获得均等糖果的最小代价。

不妨假设某个最优解中每个人只能向位于其右手边的人传递糖果，传递的糖果分别是 $a_1, a_2, \cdots, a_n$，这里，$a_i$ 可能是负数，表示实际上从位于其右手处的人收到糖果 $|a_i|$。那么，获得均等糖果的代价即为 $\displaystyle \sum_{i = 1}^n|a_i|$。我们可以断言：

断言

必然存在某个最优解，满足 $a_1 \sim a_n$ 中，至少有一项为 $0$。

证明

假设某个最优解中不存在 $0$，不妨假设这 $n$ 项中有 $x$ 项为正，$y$ 项为负。

若 $x \ge y$，不妨假设这 $x$ 项中最小的一项值为 $m$。那么，我们将所有项都减少 $m$。这依然能够保证所有人都获得均等糖果。同时，$x$ 个正数项总共减少了 $xm$，这 $x$ 个正数项的绝对值之和减少了 $xm$。$y$ 个负数项总将就减少了 $ym$，它们的绝对值之和增加了 $ym$。所有的 $n$ 项绝对值之和总共减少了 $(x - y)m$，因为 $x \ge y$，可以得知新的解不会比原来的解差。我们得到了一个包含有一项为 $0$ 的最优解。

$x \le y$ 同理。

---

如果我们通过枚举没有发生传递的位置来计算最优解，那么时间复杂度为 $O(n^2)$，无法通过本题。

将每个人手中的糖果数减去平均值，求出前缀和数组为 $S[N]$。假设第 $k$ 个人和第 $k + 1$ 个人之间没有发生传递，那么，从第 $k + 1$ 开始，新的前缀和为

序号	前缀和
$k + 1$	$S[k + 1] - S[k]$
$k + 2$	$S[k + 2] - S[k]$
$k + 3$	$S[k + 3] - S[k]$
$\vdots$	$\vdots$
$n$	$S[n] - S[k]$
$1$	$S[n] + S[1] - S[k]$
$2$	$S[n] + S[2] - S[k]$
$3$	$S[n] + S[3] - S[k]$
$\vdots$	$\vdots$
$k$	$S[n] + S[k] - S[k]$

注意到我们已经将每个位置手中的糖果数量减去了平均值，那么 $S[n] = 0$，上面的表格变为

序号	前缀和
$k + 1$	$S[k + 1] - S[k]$
$k + 2$	$S[k + 2] - S[k]$
$k + 3$	$S[k + 3] - S[k]$
$\vdots$	$\vdots$
$n$	$S[n] - S[k]$
$1$	$S[1] - S[k]$
$2$	$S[2] - S[k]$
$3$	$S[3] - S[k]$
$\vdots$	$\vdots$
$k$	$S[k] - S[k]$

按照第二题推导的结论，总共的代价为每个位置前缀和的绝对值之和，而代价的最小值什么时候取到呢？当 $S[k]$ 为 $S[1]$、$S[2]$、$\cdots$、$S[n]$ 的中位数的时候取得。

例4. 七夕祭

例5. 动态中位数

动态中位数

依次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数。

我们建立两个二叉堆，一个小根堆，一个大根堆，设当前序列长度为 $M$，我们始终保持：

• 序列中从小到大排名为 $1 \sim M/2$ 的整数存储在大根堆中；
• 序列中从小到大排名为 $M/2 + 1 \sim M$ 的整数存储在小根堆中。（无论 $M$ 奇、偶，中位数均位于小根堆堆顶）

当新进来一个数 $X$。 若 $X$ 小于中位数，则将 $X$ 插入大根堆，否则插入小根堆。然后检查并维护上面的性质。