描述
农夫 John 建造了一座很长的畜栏，它包括N (2 <= N <= 100,000)个隔间，这些小隔间依次编号为x1,…,xN (0 <= xi <= 1,000,000,000).
但是，John的C (2 <= C <= N)头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢？
输入
有多组测试数据，以EOF结束。
第一行：空格分隔的两个整数N和C
第二行——第N+1行：分别指出了xi的位置
输出
每组测试数据输出一个整数，满足题意的最大的最小值，注意换行。
样例输入
5 3
1
2
8
4
9
样例输出
3
解题思路：此题表达的意思是：把 C头牛放进 N个带编号的隔间中，使得任意两头的隔间距离（位置的最小差值）最大。以输入样例为例，将3头牛放进编号为1、4、8的隔间，则这3头牛所在的隔间的距离为3、4、7，最短距离为 3.不可能找到比 3还要大的最小距离。假设任意两头牛的编号差值都大于3，考虑贪心算法，按间隔编号从小到大分配，第一头牛放进编号1的隔间，则第二头牛至少需要放进编号8的隔间，此时，第三头牛只能进入编号9的隔间，而9-8=1<3，与假设矛盾。
这道题是一个最小值最大化的问题。这类问题不易直接求解，可尝试简化问题，将求最小值问题转化为判断性问题：判断最小距离为X时是否可放下C头牛。那么目标就转化为从小到大枚举X，判断是否可行，直到找到第一个可行的X，则这个X就是答案。为了进一步加快算法速度，可使用二分查找替换顺序枚举。
因此，问题现在转化为判定性问题和二分查找
（1）判断问题：使用贪心算法，对隔间的编号从小到大的排序，从最小编号的隔间开始，每次分配距离尽可能近的隔间，看最后能否分配下C头牛
（2）二分查找：最小距离left=0，最大距离right=L[N-1]-L[0]。此时的二分查找是要找到最小满足条件的目标元素，相当于查找重复出现的元素第一次出现的位置。也要注意循环结束的条件和返回值。
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int INF = 9999999;
//输入
int N,M;
int x[100];
//判断是否满足条件
bool C(int d){
int last = 0;
for(int i=1;i<M;i++){
int crt = last + 1;
while(crt < N && x[crt] - x[last] < d){
crt++;
}
if(crt == N)
return false;
last = crt;
}
return true;
}
void solve(){
//最开始时对 x数组排序
sort(x,x+N);
//初始化解的存在范围
int lb = 0;
int ub = INF;
while(ub - lb > 1){
int mid = (lb + ub)/2;
if(C(mid)){
lb = mid;
} else{
ub = mid;
}
}
printf("%d\n",lb);
}
int main(){
cin>>N>>M;
for(int i=0;i<N;i++){
cin>>x[i];
}
solve();
return 0;
}
有什么不懂可以在评论区问我，我会及时回答的，感谢阅读，希望能帮到您！
