题目描述
农夫 John? 建造了一座很长的畜栏，它包括 N (2 ≤ N ≤ 100,000)个隔间，这些小隔间依次编号为x1,…,xN(0 ≤ xi ≤ 1,000,000,000)。 但是，John?的 C(2 ≤ C ≤ N)头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。John?决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最小距离的最大值是什么呢？
输入格式
第一行：空格分隔的两个整数 N?和 C?；
第二行---第 N+1?行：i+1?行指出了xi的位置。
输出格式
一个整数，最小距离的最大值。
输入样例
5 3
1 2 8 4 9输出样例
3样例解释
把牛放在1，4，8这样最小距离是3。
代码如下：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m;
const int N = 1e5 + 10;
int a[N];
bool c(int x) {
int last = 0; //初始化为第一个牛舍的位置的下标
for(int i = 1; i < m; i ++) {
// i从1开始判断，而不是从0开始，是因为一开始就比较了第一个牛舍和第二个牛舍
int crt = last + 1;
while(crt < n && a[crt] - a[last] < x) {
crt ++;
}
if(crt == n) return false;//此时牛舍已经用完，但是牛还没放完，所以失败
last = crt; // 当a[crt] - a[last] >= x，表明可以放下一头牛时，将last更新为crt
}
return true; // 当所有的牛都能放完，表明成功，返回true
}
void solve() {
sort(a, a + n);
int l = 0, r = a[n - 1] - a[0];
int mid;
while(l < r) { //标准二分模板
mid = (l + r) >> 1;
if(c(mid)) l = mid + 1; // 根据具体情况进行分析判断选择
else r = mid;
}
cout << l - 1;
/*
假设到了最后一个成立的答案mid，此时l = mid + 1 ，那么下一个必定不成立并l = r退出，
此时答案其实为l - 1
*/
}
int main()
{
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
solve();
return 0;
}
