【题解】愤怒的牛
【题目描述】
农夫 John 建造了一座很长的畜栏，它包括N(2<=N<100000)个隔间，这些小隔间依次编号为x1,x2,...xn(0<=xi<=1000000000)。但是，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。
【样例解释】
N=5,表示5个畜栏。C=3,表示3头牛。
把C头牛放到N个带有编号的隔间里，使得任意两头牛所在的隔间编号的最小差值最大。例如样例排完序后变成1 2 4 8 9，那么1位置放一头牛，4位置放一头牛，它们的差值为3；最后一头牛放在8或9位置都可以，和4位置的差值分别为4、5，和1位置的差值分别为7和8，不比3小，所以最大的最小值为3。
题目要保证两头牛的最小距离尽可能大，也就是畜栏的编号尽可能大。注意，牛没有编号，认为所有的牛都是一样的。
所以这道题目实际上是在说，从给定的编号中去选一堆编号，选编号的原则就是距离越大越好。
【题目分析】
最小值最大化问题(二分搜索)
题目要求是把牛关到畜栏里面，而且题目保证牛的数量C比畜栏的数量小。
注意，题目中畜栏的编号不一定是有序的。
步骤：
C(d)：安排牛的位置使得最近的两头牛的距离不小于d
求满足C（d）最大的d。
C(d)可以安排牛的位置使得任意的牛之间的距离都不小于d
先对隔间编号从小到大排序，则最大距离不会超过两端的两头牛之间的差值，最小值为0。所以我们可以通过二分枚举最小值来求。假设当前的最小值为x，如果判断出最小差值为x时可以放下C头牛，说明当前的x有点小，就先让x变大再判断；如果放不下，说明当前的x太大了，就先让x变小然后再进行判断。直到求出一个最大的x就是最终的答案。
【参考答案】
#include<bits/stdc++.h> using namespace std; int a[100005],n,c; int judge(int mid) { int i,count=1,t=a[0]; //count是指放了几头牛，从1开始。t用来表示当前的房间号 for(i=1; i<n; i++) { if(a[i]-t>=mid)//判断两个房间之间的距离 { count++; t=a[i];//修改t的值，即修改当前房间号，例如原来t=1,a[2]=4,若a[2]-t>=mid符合，那么t=4,然后算a[3]或者a[4]与t之间的距离。 if(count>=c)//可以放下C头牛 return 1; } } return 0; } int binary()//二分搜索符合条件的最小距离的最大值 { int low=0,high=a[n-1]-a[0],mid; while(low<=high) { mid=(low+high)/2;//mid即为最小房间号与最大房间号之间的距离 if(judge(mid)) low=mid+1;//所求距离>=mid，可以继续增大试探 else high=mid-1;//所求距离<mid，所以必须减小来试探 } return low-1; //由于在之前距离+1，所以此时-1 } int main() { while(scanf("%d%d",&n,&c)) { int i; for(i=0; i<n; i++) scanf("%d",&a[i]); sort(a,a+n); printf("%d\n",binary()); } return 0; }(adsbygoogle = window.adsbygoogle || []).push({});