一道关于距离和的数学题

题意

给定数轴上$n$个点$a_i,i\in[1,n]$，$(a_i<a_{i+1},i<n)$求$sum=\sum\limits_{i=1}^n|x-a_i|$的最小值。

---

思路

1.从$-\infty$开始向右移动，显然移动$\triangle x$，$sum$是递减的，继续往右移动，当左边的点等于右边的点时达到最小值，继续往右移动，$sum$会递增。

所以需要讨论$n$的奇偶性。

当$n=2k-1$时，显然$x=k$取最小值，为

$\sum\limits_{i=1}^{k-1} (a_{n+1-i}-a_i)$

当$n=2k$时，$x\in[k,k+1]$之间都可以取到最小值，为

$\sum\limits_{i=1}^{k} (a_{n+1-i}-a_i)$

---

2.由绝对值不等式：$|a|+|b|\ge|a-b|$的取等条件：$ab\le0$

$n=2k-1$时：

$\sum\limits_{i=1}^n|x-a_i|$

$=(|x-a_1|+|x-a_n|)+(|x-a_2|+|x-a_{n-1}|)+\dots+|x-a_k|$

$\ge (a_n-a_1)+\dots+|x-a_k|$

当$x=k$时取等。

偶数同理。

---

推广

$Butchart-Moster$定理：

设$a_1<\dots<a_n,\lambda_1\dots \lambda_n\in Q^+,$则$f(x)=\sum\limits_{i=1}^n\lambda_i|x-a_i|$存在唯一极小值。

ACM中的应用

显然该数学题，可以与$ACM$中的贪心的题相联系，给定$n$个点，求距离这个$n$个点的和最小值，可以因为是个凹型函数，可以考虑三分，但是本题已经证明了只需考虑奇偶性，所以就直接贪心了。