M9A???. 愤怒的奶牛 / 最大最小距离

题目背景

原题来自 USACO 2005 Feb. Gold。

农夫约翰建造了一排牛舍，共有 n 个牛舍，位置分别为 x_i。现在要把 m 头牛放进这些牛舍中，每个牛舍最多放一头牛。

由于奶牛之间容易互相攻击，约翰希望把它们安排得尽可能分散。也就是说，希望 任意两头牛之间的最小距离尽可能大。

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

---

题目描述

给定 n 个牛舍的位置 x_i，以及 m 头牛。
请把这 m 头牛放入这些牛舍中，使得：

• 每个牛舍最多放一头牛；
• 设所有已放入奶牛的两两距离中的最小值为 d；
• 需要让这个 d 尽可能大。

输出这个最大的最小距离。

---

输入格式

第一行两个整数 n, m。
第二行 n 个整数 x_i，表示每个牛舍的位置。

---

输出格式

输出一个整数，表示最大的最小距离值。

---

样例 #1

输入

5 3
1 2 8 4 9

输出

3

---

样例说明

先将牛舍位置排序后得到：

1 2 4 8 9

如果把 3 头牛放在位置 1、4、8 的牛舍中，那么最近两头牛之间的距离为：

• 4 - 1 = 3
• 8 - 4 = 4

最小值为 3。

可以证明，不存在一种放法使这个最小值大于 3，所以答案是 3。

---

数据范围

对于 100% 的数据，保证：

• 2 ≤ n ≤ 10^5
• 2 ≤ m ≤ n
• 0 ≤ x_i ≤ 10^9

---

提示

这是一个经典的 二分答案 问题。

思路概述

1. 先将牛舍位置从小到大排序；
2. 二分枚举答案 d，表示“最近两头牛之间的最小距离至少为 d 是否可行”；
3. 贪心检查：
   • 第一头牛放在最左边的牛舍；
   • 之后每头牛都尽量放在当前能放的最左边牛舍；
   • 如果最终能放下至少 m 头牛，说明这个 d 可行；
4. 二分求出最大的可行值。

---

参考复杂度

• 排序：O(n log n)
• 每次检查：O(n)
• 总复杂度：O(n log V)，其中 V 为坐标范围

---

输入输出约定

• 输入数据中牛舍位置不一定有序；
• 输出仅一个整数，不要输出多余空格或文字。