农夫约翰建造了一座有n间牛舍的小屋，牛舍排在一条直线上，第i间牛舍在xi的位置，但是约翰的m头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。
牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？
5 3
1 2 8 4 9
3
#include<cstdio> #include <map> #include<iostream> #include<string> #include<cstring> #include<cmath> #include<algorithm> using namespace std; inline int read() {int x=0,f=1;char c=getchar();while(c!=‘-‘&&(c<‘0‘||c>‘9‘))c=getchar();if(c==‘-‘)f=-1,c=getchar();while(c>=‘0‘&&c<=‘9‘)x=x*10+c-‘0‘,c=getchar();return f*x;} typedef long long ll; const int maxn=1e6+5; int n,m; int a[maxn]; int judge(int x){ int cnt=1; int t=0; for(int i=1;i<n;i++){ if(a[i]-a[t]>=x){ cnt++; t=i; } } if(cnt>=m){ return 1; } return 0; } int main(){ cin>>n>>m; for(int i=0;i<n;i++){ cin>>a[i]; } sort(a,a+n); int l=a[0],r=a[n-1]-a[0]; int ans; while(l<=r){ int mid=(l+r)/2; if(judge(mid)){ l=mid+1; ans=mid; } else{ r=mid-1; } } printf("%d",ans); }
原文：https://www.cnblogs.com/lipu123/p/12242758.html