242046 - 候鸟观测点布设

题目描述

一片狭长湿地沿直线延伸,工作人员选出了 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】

选择坐标1、4、8,三个两两距离为3、7、4,最小值为3。不能选出三个两两距离均至少为4的位置,因此答案为3。

【样例解释2】

必须选中两个候选位置,它们相距5,因此答案为5。

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 4
通过人数 2
金币数量 5 枚
难度 提高


上一题 下一题