POJ-2456 Aggressive cows

题面

【VJudge】 【POJ】

农夫约翰搭建了一间有N间牛舍的小屋。牛舍排在一条线上，第i号牛舍在Xi的位置。但是他的M头牛对小屋很不满意，因此经常相互攻击。约翰为了防止牛之间相互伤害，因此决定把每头牛都放在离其他牛尽可能远的牛舍。求最近的两头牛之间距离的最大值。

总结

二分答案，选中第一个牛棚，然后按照至少相隔x距离放牛，判断能不能放下这么多头牛。

槽点

1. (CE) POJ不支持万能头！
2. (TLE) 误将最远的那个点设成n（实际上应为a[n]），且因为选中了指定数量的牛棚之后就不需要继续选了可以直接跳出判定。

AC代码

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int ai[100005],n,c,l,r,mid,cnt,tmp;
int main(){
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++){
        scanf("%d",&ai[i]);
    }
    sort(ai+1,ai+n+1);
    l=1,r=ai[n];
    while(l<r){
        mid = (l+r+1)>>1;cnt=1;tmp=1;
        for(int i=2;i<=n;i++){
            if(ai[i]-ai[tmp]>=mid){
                tmp=i;cnt++;
            }
            if(cnt>=c)break;
        }
        if(cnt>=c){
            l=mid;
        }else{
            r=mid-1;
        }
    }
    printf("%d\n",l);
    return 0;
}

页面： 1 2 3 4 5 6