题目链接: http://poj.org/problem?id=2456
题目大意：n个房子，m头牛，房子有一个横坐标，问将m头牛塞进房子，每两头牛之间的最大间隔是多少。
解题思路：
不难看出应该二分房子间隔，找一个最大的可行间隔。
首先将房子坐标排序，这样只需从第1个房子开始塞牛就行了，且第一个房子肯定得塞一只牛，才能保证空间的有效利用。
这样，每次对于一个间隔，从第一个房子开始塞牛：
①如果上一个房子坐标last+间隔<=h[i],那么这个房子肯定得塞牛，才能有效利用空间，更新last，cnt++。
②否则不能塞牛，去下一个房子。
这样，只要最后cnt>=m,这个间隔就是可行的。
关键在于确定二分的边界，左边界l可以确定是排序之后相邻两个房子的差的最小值。这也是可以尝试的最小间隔。
我一开SB地认为右边界就是两个相邻两个房子差的最大值。其实不对，因为牛之间可以隔好多房子。其实r=h[n]-h[1]/(m-1)
如果你比较机智而且又懒，其实l=0，r=h[i]就行了，反正范围大点也不会超时orz。
以后确定范围直接脑残0~最大好了。
#include "cstdio" #include "algorithm" using namespace std; int h[100005],n,m,ans; bool check(int dist) { int cnt=1,last=h[1]; for(int i=2;i<=n;i++) if(last+dist<=h[i]) {last=h[i];cnt++;} if(cnt>=m) return true; else return false; } int main() { //freopen("in.txt","r",stdin); int l=0x3f3f3f3f,r=-1; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&h[i]); sort(h+1,h+n+1); for(int i=2;i<=n;i++) l=min(l,h[i]-h[i-1]); r=(h[n]-h[1])/(m-1); while(l<=r) { int mid=l+(r-l)/2; if(check(mid)) {ans=mid;l=mid+1;} else r=mid-1; } printf("%d ",ans); }
| 13591899 | neopenx | 2456 | Accepted | 548K | 110MS | C++ | 661B | 2014-11-02 19:22:27 |