程序设计能力实训

1238. 星巴克连锁店

单点时限: 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)$。

输出格式

输出一行整数,表示最大的最近距离。

样例

Input
6 3
1
3
5
2
7
9
Output
4
Input
5 4
5
7
10
28
9
Output
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$。

不限期开放

题目列表