绝对值不等式
2025-11-16
简介
若存在 n 个单调不减数记作 a1 到 an,将其放置在数轴上,此时若想取一点 x,使得 ∣a1−x∣+∣a2−x∣+...+∣an−x∣ 最小,则 x 应取在中间点处。
证明
考虑仅存在两个数 a1 和 a2,则 ∣a1−x∣+∣a2−x∣≥∣a1−a2∣。
扩展到 n 个数,则可以将 a1 和 an 放一组,直到全部配对或剩一个,若全部配对则可以任意取 a2n 到 a2n+1 中的一点,若仅剩一个则取那一个数的位置。
这个过程也可以理解为每次固定左右两端的范围,然后依次缩小。
所以绝对值不等式一般形式为:
∣a1−x∣+∣a2−x∣+...+∣an−x∣≥∣a1−an∣+∣a2−an−1∣+...
若 n 为奇数则后面还有一项下标为 ⌈2n⌉。
如果要求最小值,只需要把中间点下标看作 ⌊2n⌋
重要
可以使用 nth_element 将时间复杂度优化至 O(n)。
实际上,如果注意力惊人会发现:
i=1∑n∣ai−a2n∣=i=1∑n∣ai−a2i∣
证明如下
- 若 n 为奇数。
将第一项展开,可以得到:i=1∑n∣a1−a2n∣=共2n−1项(an−a2n)+(an−1−a2n)+...+(a2n−a2n)+共2n−1项...+(a2n−a2)+(a2n−a1)=a2n+1+a2n+2+...+an−1+an−a0−a1−...−a2n−2−a2n−1
将右侧展开,可以得到:i=1∑n∣ai−a2i∣=a1+a2+...+an−1+an−2(a1+a2+...+a2n−1)−a2n=a2n+1+a2n+2+...+an−1+an−a0−a1−...−a2n−2−a2n−1
证毕。 - 若 n 为偶数。
同理。
扩展
- 扩展到 d 维空间 算法:模拟退火
