题目描述
农夫约翰建造了一座有 n 间牛舍的小屋，牛舍排在一条直线上，第 i 间牛舍在 xi 的位置，但是约翰的 m 头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。
牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。约翰决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？
【样例解析】把牛放在 1，4，8 这三个位置，距离是 3。容易证明最小距离已经最大。
【数据范围】对于 100% 的数据，2≤n≤10^5，0≤xi≤10^9，2≤m≤n。不保证 x 数组单调递增。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
usingnamespacestd;
intA[1000010];
intn,c,a;
boolcheck(intx)//判断此答案是否可行
{
intnum=0;
intl=A[1];//l记录上一只牛的位置，开始时第一只牛一定在第一个牛栏
for(inti=2;i<=n;i++)//依次枚举每个牛栏
{
if(A[i]-l<x) num++;//若此距离不满足当前答案，那么需要的牛栏数+1，即把当前牛放到下一个牛栏
elsel=A[i];//否则就更新上一次的牛栏位置 ，即上一头牛放的位置
if(num>a)returnfalse;// 若需要牛栏数大于最大牛栏数，此答案不可行
}
returntrue;//反之，若需要牛栏数小于最大需要牛栏数，此答案可行
}
intmain()
{
scanf("%d%d",&n,&c);
for(inti=1;i<=n;i++)
scanf("%d",&A[i]);
sort(A+1,A+n+1);//由于无序，需排序（sort默认从小到大，不用写规则）
a=n-c;//最大剩余牛栏数
intl=1;//二分的左界，从1开始，即可能情况的最小值
intr=A[n]-A[1];//二分右界，即可能情况的最大值
while(l+1<r)//若左<右，则继续二分答案
{
intmid=(l+r)/2;//二分 两区间分别为l ~ mid ， mid ~ r;
if(check(mid)) l=mid;//若此答案可行，从mid ~ r区间继续查找（更大答案），即修改左界l=mid
elser=mid;//反之，若此答案不可行，从l ~ mid区间查找（合理答案），即修改左界l=mid
}
if(check(r))printf("%d",r);//若可行解为右界，输出右界
elseprintf("%d",l);//若可行解为左界，输出左界
return0;
}