首页 > 代码库 > HDU 4004

HDU 4004

2024-08-05 07:46:00   214人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4004

题意：青蛙过长L的河，只能落在石头上，石头数量是n，给出n个坐标，至多跳m次，求在可以过河的条件下，青蛙跳的最大距离的最小值

水题，二分答案即可，验证的时候青蛙显然应尽可能落在远端

#include <iostream>#include <cstdio>#include <cstring>#include <map>#include <algorithm>#include <queue>#include <cmath>#include <stack>#include <set>using namespace std;int L,n,m;int a[500005];int OK(int x){    int now=0;    if(x>=L)return 1;    if(n>=1 && x>=a[n-1]){        if(x>=L-a[n-1] && m>=2)return 1;        return 0;    }    int cnt=0;    for(int i=0;i<n-1;i++){        if(now+x>=a[i] && now+x<a[i+1]){            now=a[i];            cnt++;        }    }    if(now+x>=L){        cnt++;        if(cnt<=m)return 1;        return 0;    }    if(now+x>=a[n-1]){        cnt++;        now=a[n-1];        if(now+x>=L){            cnt++;            if(cnt<=m)return 1;            return 0;        }        else return 0;    }    return 0;}int main(){    while(~scanf("%d%d%d",&L,&n,&m)){        for(int i=0;i<n;i++)            scanf("%d",&a[i]);        sort(a,a+n);        int l,r;        l=0;r=1000000000;        while(r-l>=5){            int mid=(l+r)>>1;            if(OK(mid))r=mid;            else l=mid;        }        for(int i=l;i<=r;i++){            if(OK(i)){                printf("%d\n",i);                break;            }        }    }    return 0;}
View Code

 

HDU 4004


联系
我们