题目链接: 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[],n,m,ans;
bool check(int dist)
{
int cnt=,last=h[];
for(int i=;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=-;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&h[i]);
sort(h+,h+n+);
for(int i=;i<=n;i++) l=min(l,h[i]-h[i-]);
r=(h[n]-h[])/(m-);
while(l<=r)
{
int mid=l+(r-l)/;
if(check(mid)) {ans=mid;l=mid+;}
else r=mid-;
}
printf("%d\n",ans);
}
| 13591899 | neopenx | 2456 | Accepted | 548K | 110MS | C++ | 661B | 2014-11-02 19:22:27 |