绝对值和与加权中位数

绝对值的线性组合是连续分段一次函数。先讨论任意实系数的逐段计算，再说明正权重如何产生加权中位数；只有正权重情形才能解释为加权总距离。

允许负系数时：逐段斜率与全部最值候选

设

F(x)=\sum_{i=1}^{n}w_i|x-b_i|,\qquad b_1<\cdots<b_n,\quad w_i\in\mathbb R.

记 $W=\sum_iw_i$ 、 $B=\sum_iw_ib_i$ 。相同的 $b_i$ 应先合并系数，系数为零的项可以删去。若全部系数为零，函数恒为零。

在 $b_j<x<b_{j+1}$ 内，前 $j$ 项的绝对值取 $x-b_i$ ，其余取 $b_i-x$ ，所以

F(x)=\left(2\sum_{i\le j}w_i-W\right)x+B-2\sum_{i\le j}w_ib_i.

令 $s_j=2\sum_{i\le j}w_i-W$ ，并约定 $s_0=-W,s_n=W$ 。这给出了从最左段到最右段的全部斜率；跨过 $b_j$ 时斜率变化为 $2w_j$ 。

负系数使斜率可能下降，因此不能再使用加权中位数判据。两端斜率总互为相反数，但中间斜率不一定两两相反；只有额外的系数对称性才能保证这种结构。

每段按 $s_j>0,=0,<0$ 分别递增、恒定、递减。
折点 $b_j$ 是局部极小值点，当且仅当 $s_{j-1}\le0\le s_j$ ；局部极大值点对应 $s_{j-1}\ge0\ge s_j$ 。两侧严格异号才是严格局部极值。
非零斜率的段内部没有极值；零斜率的段上所有点取同一个值，按非严格定义可同时是局部极大、极小值点。

全局情形由两端表达式

F(x)=-Wx+B\ (x\le b_1),\qquad F(x)=Wx-B\ (x\ge b_n)

决定：

表中最后一行的两端都是常值，分别等于端点 $F(b_1),F(b_n)$ ，所以没有遗漏。找到最值数值后，还须把取到相同值的零斜率线段或射线加入全部最值点集。

若定义域限制在闭区间，只须比较区间端点及内部折点；每个子区间上函数是一次函数，其值介于两端之间。这也说明该算法为何不重不漏。

设 $w_i>0$ 、 $a_i\in\mathbb R$ ，记

F(x)=\sum_{i=1}^n w_i|x-a_i|,\qquad W=\sum_{i=1}^n w_i.

在不含任何 $a_i$ 的开区间内，各绝对值的符号固定，斜率为

\sum_{a_i<x}w_i-\sum_{a_i>x}w_i.

每经过一个折点，斜率增加该点总权重的两倍，因此斜率只会上升。重复的 $a_i$ 应合并其权重；若有 $r$ 个互异折点，才有 $r+1$ 个开区间段。

零权重项可以删去。负权重不属于本节结论，例如 $-|x|$ 在实轴上没有最小值。

固定 $x$ ，记其严格左侧、严格右侧及恰在该点的总权重分别为 $L,R,E$ ，故 $W=L+R+E$ 。在该点两侧紧邻的小区间内，斜率分别为

s_-=L-R-E=2L-W,\qquad s_+=L+E-R=W-2R.

若 $s_->0$ ，向左移动能降低函数值；若 $s_+<0$ ，向右移动能降低函数值。因此取得最小值必须满足

L\le W/2,\qquad R\le W/2.

反过来，这两个条件使左侧紧邻斜率非正、右侧紧邻斜率非负。因为斜率只会上升，更左侧所有段的斜率也非正，更右侧所有段也非负，所以该点确为全局最小值点。

这样的点称为加权中位数。注意比较的是严格位于左右两侧的权重，而不是把当前点的权重同时计入两边。

将数据按 $a_1\le\cdots\le a_n$ 排列，所有权重取 $1$ 。

当 $n=2m$ 时，全部最小值点构成区间 $[a_m,a_{m+1}]$ ，最小值为

\sum_{i=m+1}^{2m}a_i-\sum_{i=1}^m a_i.

当 $n=2m+1$ 时，唯一最小值点为 $a_{m+1}$ ，最小值为

\sum_{i=m+2}^{2m+1}a_i-\sum_{i=1}^m a_i.

空和按 $0$ 计算，故也适用于 $n=1$ 。偶数情形的中间两个数相等时，最小值区间退化为一点。

另一种证明是将最左与最右配对： $|x-a|+|x-b|\ge b-a$ （ $a\le b$ ），等号恰在 $x\in[a,b]$ 时成立。各对取等区间的交集给出偶数情形的中间区间；奇数情形剩下的一项迫使 $x$ 等于中位数。

设 $F(x)=2|x|+|x-2|+3|x-5|$ ，总权重为 $6$ 。在 $0,2,5$ 分隔出的四段上，斜率依次为 $-6,-2,0,6$ ，因此全部最小值点为 $[2,5]$ 。代入 $x=2$ 得最小值为 $13$ 。

若另限 $x\in[3,4]$ ，整个区间都取最小值 $13$ ；若限 $x\in[-2,1]$ ，只在最右端 $x=1$ 取最小值 $15$ ；若限 $x\in[6,8]$ ，只在最左端 $x=6$ 取最小值 $19$ 。

一般地，设无约束最小值区间为 $[u,v]$ 。闭约束区间与它相交时，交集就是全部最小值点；完全在它左边时取约束右端，完全在右边时取约束左端。开区间还须检查候选端点是否允许取到，可能只有下确界。

在正权重、定义域为整个实轴的条件下，设最小值为 $M$ ，最小值点集为 $[u,v]$ 。函数在 $(-\infty,u)$ 严格递减，在 $(v,+\infty)$ 严格递增，并在两端任意大。

所以 $F(x)=c$ 在 $c<M$ 时无解； $c=M$ 时解集为 $[u,v]$ ； $c>M$ 时恰有两个解，分别在最小值区间两侧。

相应地， $F(x)\le c$ 在 $c<M$ 时为空集，在 $c=M$ 时为 $[u,v]$ ，在 $c>M$ 时为以那两个根为端点的闭区间。求两个根时再按折点定位并解一次方程，通常比一开始展开全部区间简便。