单点时限: 2.0 sec
内存限制: 256 MB
jxtxzzw喜欢喝星巴克。
上海有很多地铁。
jxtxzzw想要建立上海地铁沿线的星巴克连锁店,现在要在一条铁路线的所有车站里,选择一部分车站,这些车站里面需要开设星巴克门店。
为了简化问题,我们假设上海地铁某号线为一条直线。
其中每个站点的坐标为$x_1,x_2,\cdots , x_n$。
jxtxzzw一共要开办$m$个星巴克连锁店,并且不希望连锁店离得太近,以使得整体的收益最大化。
jxtxzzw希望星巴克连锁店之间的最近距离尽可能大。
你能帮他算出这个最大的最近距离吗?
(断句没问题?没错。最大的·最近距离。)
第一行输入用空格分隔的两个整数$n,m$ $(2 \le n \le 10^5, 2 \le m \le n)$,分别表示车站数量和连锁店数量。
接下来一共$n$行,每行一个整数$x_i$ $(0 \le x_i \le 10^9)$。
输出一行整数,表示最大的最近距离。
6 3 1 3 5 2 7 9
4
5 4 5 7 10 28 9
2
样例$2$说明,一共有$5$种选择方案。
5 7 9 10
,最近距离为$min(7-5,9-7,10-9)=1$5 7 9 28
,最近距离为$min(7-5,9-7,28-9)=2$5 7 10 28
,最近距离为$min(7-5,10-7,28-10)=2$7 9 10 28
,最近距离为$min(9-7,10-9,28-10)=1$5 9 10 28
,最近距离为$min(9-5,10-9,28-10)=1$因此,最大的最近距离为$2$。