对于在数轴上的 (n) 个点，要集合所有点于同一位置，使得移动的曼哈顿距离之和最小，那么应该选取哪个点呢？
设有 (n) 个点， (i) 点的位置为 (x_i) ，且有 (x_i \le x_{i+1} \ (i=0,1,2 \dots, n – 1))
则对于 (k) 点，距离之和为：
[\begin{align} \sum_{i=0}^{n-1} |x_i-x_k| & = \sum_{i=0}^{k}(x_k-x_i) + \sum_{i=k+1}^{n-1}(x_i-x_k)\ & =(k + 1) * x_k – \sum_{i=0}^{k}x_i + \sum_{i=k+1}^{n-1}x_i – (n – k – 1) * x_k \ & = (2k – n) * x_k – \sum_{i=0}^{k}x_i + \sum_{i=k+1}^{n-1}x_i \ \end{align}]
同理，对于 (k+1) 点，距离之和为：
[\ \sum_{i=0}^{n-1} |x_i-x_{k+1}| = (2k – n + 2) * x_{k+1} – \sum_{i=0}^{k+1}x_i + \sum_{i=k+2}^{n-1}x_i ]
那么对于选择相邻两点时，距离之和的变化差值 (\Delta) 有:
[\begin{align} \Delta &= \sum_{i=0}^{n-1}|x_i-x_{k+1}| – \sum_{i=0}^{n-1}|x_i-x_{k}|\ & = [(2k – n + 2) * x_{k+1} – \sum_{i=0}^{k+1}x_i + \sum_{i=k+2}^{n-1}x_i] – [(2k – n) * x_k – \sum_{i=0}^{k}x_i + \sum_{i=k+1}^{n-1}x_i]\ & = (2k-n)(x_{k+1}-x_k) \end{align}]
因为有 (x_{k+1} \ge x_k)，则 (\Delta) 的取值为：
[\left{ \begin{array}{lr} \Delta < 0, & 2k < n \ \Delta = 0, & 2k = n \ \Delta > 0, & 2k > n \ \end{array} \right. ]
可见，(2k < n) 时，随着 (k)，距离之后逐渐减小，(2k > n) 时，随着 (k)，距离之后逐渐增大
则在 中点处取的距离之和的最小值
Original: https://www.cnblogs.com/Code-CHAN/p/15389874.html
Author: Code-CHAN
Title: 最小化一维曼哈顿距离的简单证明
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/715355/
转载文章受原作者版权保护。转载请注明原作者出处！