题目描述

原题来自：USACO 2005 Feb. Gold。

农夫约翰有 n 间牛舍，牛舍排在一条直线上，第 i 间牛舍的位置为 x_i。

现在要把 m 头牛放进这些牛舍中。为了避免牛互相攻击，希望任意两头牛之间的最小距离尽可能大。

请你求出这个“最大的最小距离”。

换句话说：

在 n 个位置中选出 m 个位置， 使得被选位置之间的最小距离最大。

输入格式

第一行包含两个整数 n 和 m。

第二行包含 n 个整数，表示每个牛舍的位置 x_i。

输出格式

输出一个整数，表示任意两头牛之间最小距离的最大可能值。

输入数据 1

5 3
1 2 8 4 9

输出数据 1

3

样例解释

将牛放在位置：

1 4 8

此时相邻两头牛之间的距离分别为：

3 4

最小距离为 3。

也可以放在：

1 4 9

最小距离同样为 3。

无法让最小距离达到 4，所以答案是 3。

数据范围与提示

对于 100% 的数据：

2 <= n <= 100000
0 <= x_i <= 1000000000
2 <= m <= n

本题可以使用二分答案。

可以猜测一个距离 d，然后判断：

能不能放下 m 头牛，并且任意相邻两头牛之间的距离都至少为 d？

如果可以，说明 d 可行，可以继续尝试更大的距离。

如果不可以，说明 d 太大，需要缩小。