【poj3258】River Hopscotch

野性酷女 2022-09-24 07:23 29阅读 0赞

![这里写图片描述][20160727174330784]  
![这里写图片描述][20160727174339738]  
![这里写图片描述][20160727174348363]

这题虽是二分的题，但感觉就是别扭，很难想清楚怎么设置判断。我也是看了别人的判断过程及判断依据后才成功ac。值得收藏的二分题。  
判断的过程我尽量解释一下，有不清楚的地方请参阅网址：  
[http://www.cnblogs.com/jingqi814/p/3581553.html][http_www.cnblogs.com_jingqi814_p_3581553.html]

这样讲应该能理解的：  
1.首先去掉M个石头后两个石头之间会有最小的距离，本题让求这个最小距离的最大值。  
2.我们二分是在去掉M个石头的前提下，对可能的最小距离的区间进行二分，取值区间是0到L，目的是求那个最大的最小距离，一直去逼近那个最大的最小距离。  
3.判断的过程是只要某个区间只要小于mid，这个区间的又端石头就能去掉，因为最小的距离是mid，要不mid小的话当然要去掉，然后看能够去掉的数量的总和 和M的关系。  
4.如果大于M，肯定是mid太大了；如果小于M，太小了；如果等于M，可能是正确答案，但还要判断有没有更大的mid使符合等于M的条件。

#include<stdio.h>
    #include<algorithm>
    using namespace std;
    const int MAXN = 5*1e4+10;
    int a[MAXN];
    int L,N,M;
    bool judge(int mid) {
        int sum=0,start=0;
        for(int l=1; l<=N+1; l++) {
            if(a[l]-a[start]<mid) {
                sum++;
            } else
                start=l;
        }
        return sum<=M;
    }
    int main() {
        scanf("%d%d%d",&L,&N,&M);
        for(int l=1; l<=N; l++) {
            scanf("%d",&a[l]);
        }
        a[N+1]=L;
        sort(a+1,a+N+1);
        int l=0,r=L;
        int mid;
        int ans;
        while(l<=r) {
            mid=l+r>>1;
            if(judge(mid)) {
                ans=mid;
                l=mid+1;
            } else
                r=mid-1;
        }
        printf("%d\n",ans);
        return 0;
    }

[http://acm.hust.edu.cn/vjudge/contest/123973\#problem/G][http_acm.hust.edu.cn_vjudge_contest_123973_problem_G]

[20160727174330784]: /images/20220719/cad6ec09ef1641aa9f61507c4d31acbb.png
[20160727174339738]: /images/20220719/0fd431245df44c36892d88b388d3aef6.png
[20160727174348363]: /images/20220719/1ef6ae2d0672487fb488115f667de38e.png
[http_www.cnblogs.com_jingqi814_p_3581553.html]: http://www.cnblogs.com/jingqi814/p/3581553.html
[http_acm.hust.edu.cn_vjudge_contest_123973_problem_G]: http://acm.hust.edu.cn/vjudge/contest/123973#problem/G