对于在数轴上的 \(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\)，距离之后逐渐增大
则在中点处取的距离之和的最小值