一片狭长湿地沿直线延伸,工作人员选出了 n 个可以安装自动观测设备的位置,其坐标为 x_1,x_2,\ldots,x_n,所有坐标互不相同。
现在要从中选出恰好 k 个位置,每个选中位置安装一台设备。设备不能安装在候选位置以外,也不能在同一位置放多台。
为了让观测点尽量分散,工作人员把一个方案的“最小间距”定义为:任意两台设备之间距离的最小值。请在所有方案中,使这个最小间距尽可能大,并输出它的最大值。
输入说明:
第一行两个整数 n,k。
第二行 n 个整数 x_1,x_2,\ldots,x_n,输入顺序不一定按坐标大小排列。
对全部数据,2\le k\le n\le100000,0\le x_i\le10^9,所有坐标互不相同。
输出要求:
输出一个整数,表示能够达到的最大最小间距。
5 3 1 2 8 4 9
3
2 2 5 0
5
选择坐标1、4、8,三个两两距离为3、7、4,最小值为3。不能选出三个两两距离均至少为4的位置,因此答案为3。
必须选中两个候选位置,它们相距5,因此答案为5。