题解CF1131C【Birthday】
Rbu_nas
2019-03-02 11:14:02
题意说的已经很清楚了,$n$个人站成一圈求彼此身高最大差值的最小值。很明显的贪心。
因为是环形,所以我们将$a$数组排序,奇数下标排一起,偶数下标逆序排一起,即:
$a_1$ $a_3$ $a_5$ $...$ $a_{2n-1}$ | $a_{2n}$ $...$ $a_6$ $a_4$ $a_2$
这样的排法彼此差值最小,因为如果按相邻下标放一起,得到的差值肯定不是最优:
当$n = 5\ \ ,\ a[]={1, 2, 3, 4, 5}$ 时
$1$ $2$ $3$ $4$ $5$ $\Rightarrow{} \ max=4$
$1$ $3$ $5$ $4$ $2$ $\Rightarrow{} \ max=2$
显然可以证明,任何情况下都有奇偶排法最优
$\mathcal{Code}$
![](https://i.loli.net/2019/03/02/5c79f4a934946.jpg)