这题属于最基础的“二分答案”模型。

原题：

trick1:

看到 最大化最小值 ，显而易见有单调性，可以采用二分 来解决。

在这个问题中，假设最近两朵花的距离为 $d$：

• 如果 $d$ 是可行的（即能放下 $M$ 朵花），那么任何比 $d$ 小的距离 $d-1, d-2 \dots$ 一定也是可行的。
• 如果 $d$ 是不可行的（太宽了，放不下 $M$ 朵），那么任何比 $d$ 大的距离 $d+1, d+2 \dots$ 一定也不可行。

这种单调性允许我们在区间 $[0, 10^9]$ 内二分查找最终的答案。

trick2:

在二分过程中，我们需要一个 check(d) 函数来判定：是否存在一种方案，使得任意两朵花的间距都至少为 $d$。这里使用的是贪心策略。

为了能放下尽可能多的花（或者说为了更有可能放下 $M$ 朵花），我们在放置每一朵花时，应该在满足“距离上一朵花 $\ge d$”的前提下，选择坐标最小的那个位置。这样可以为后面剩余的花留出尽可能大的空间。

具体操作：

1. 首先将坐标数组 $x$ 排序。
2. 第 1 朵花一定放在 $x_1$（因为如果不放 $x_1$ 而放 $x_2$，后面的空间只会变小，不会变优）。
3. 遍历后续的坐标，一旦遇到 $x_i - \text{last\_pos} \ge d$，就立即种下一朵花，并更新 $\text{last\_pos} = x_i$。
4. 最后看种下的花总数是否 $\ge M$。

结合上面两个 trick，这道题就被转变成了：先对坐标排序，然后二分枚举距离 $mid$，每次用 $O(N)$ 的贪心策略 check 是否可行。若可行则尝试更大的距离（l = mid + 1），否则尝试更小的距离（r = mid - 1）。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
vector<int> x;
bool chk(int d) {
	int cnt = 1;
	int lst = x[0];
	for (int i = 1; i < n; i++) {
		if (x[i] - lst >= d) {
			cnt++;
			lst = x[i];
		}
		if (cnt >= m) return true;
	}
	return false;
}
signed main() {
	ios::sync_with_stdio(0), cin.tie(0);
	//freopen("Yukimura_Seiichi.in", "r", stdin);
	//freopen("Yukimura_Seiichi.out", "w", stdout);
	cin >> n >> m;
	x.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> x[i];
	}
	sort(x.begin(), x.end());
	int l = 0;
	int r = x[n - 1] - x[0];
	int ans = 0;
	while (l <= r) {
		int mid = l + (r - l) / 2;
		if (chk(mid)) {
			ans = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	cout << ans << endl;
	return 0;
}