[USACO16JAN]Angry Cows Silver题解

题目要求确定r的最小值，而r是有明确上下界的，所以考虑二分法:
命题P(r)表示当炸弹攻击半径为r时，k个炸弹能够覆盖全部区间。
若P(r)成立，则找到一个满足条件的r，要再尝试r能不能再缩小，反之，r太小了，要增大r的值。

如何判断P(r)是否成立？
先让l=x[0]，再跳跃到l+2r，再寻找x中最近的比l+2r大的值，以它作为新的起点，再跳跃2r,重复k次，若达到或超过x[n-1]，P(r)成立。
实现如下：

 #include<cstdio>
#include<algorithm>
const int MAXN=5e4+5;
bool P(int *x,const int &n,const int &k,int r){
    int length=x[0];
    for(int i=0;i<k;++i){
        length+=2*r;
        if(length>=x[n-1])return true;
        length=x[std::upper_bound(x,x+n,length)-x];
    }
    return false;
}
int x[MAXN];
int main(){
    int n,k;scanf("%d%d",&n,&k);
    for(int i=0;i<n;++i){scanf("%d",&x[i]);}
    std::sort(x,x+n);
    int ans=0,l=0,r=x[n-1];
    while(l<=r){
        int mid=l+(r-l)/2;
        if(P(x,n,k,mid)){
            ans=mid;
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    printf("%d\n",ans);
    return 0;
}

附评测链接备用
点我～(^_^)～