【杭电4004】The Frog's Games

Love The Way You Lie 2022-09-24 05:20 142阅读 0赞

![这里写图片描述][20160726134052116]  
![这里写图片描述][20160726134100522]

思路：本题用到了二分的思想。青蛙一次跳跃的范围是0到L（题给），然后判断在一次跳跃距离为mid时能否在m次跳跃内完成，如果能完成则用一个变量记录mid，遇到更小的符合条件的一次跳跃的距离后更新该变量的值。直接输出该变量。

#include<stdio.h>
    #include<algorithm>
    using namespace std;
    const int MAXN = 5*1e5+10;
    int a[MAXN];
    int L,n,m;
    bool judge(int u) {
        int base=0;
        int sum=0;
        for(int l=1; l<=n+1;) {
            if(base+u>=a[l]) {
                l++;
            }
            else{
                if(base==a[l-1])
                return false;
                base=a[l-1];
                sum++;
            }
        }
        sum++;
        return sum<=m;
    }
    int main() {
        while(scanf("%d %d %d",&L,&n,&m)!=EOF) {
            for(int l=1; l<=n; l++) {
                scanf("%d",&a[l]);
            }
            sort(a+1,a+n+1);
            a[n+1]=L;
            int l=0,r=L;
            int ans;//记录最小距离
            while(l<=r) {
                int mid=r+l>>1;
                if(judge(mid)) {
                    r=mid-1;
                    ans=mid;
                } else {
                    l=mid+1;
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

[http://acm.hdu.edu.cn/showproblem.php?pid=4004][http_acm.hdu.edu.cn_showproblem.php_pid_4004]

[20160726134052116]: /images/20220719/6a2d1a23e7374516807466f2e3303f9e.png
[20160726134100522]: /images/20220719/f225af4ef7f74b05bc17c2182d68a048.png
[http_acm.hdu.edu.cn_showproblem.php_pid_4004]: http://acm.hdu.edu.cn/showproblem.php?pid=4004