hdoj 5037 Frog 【万恶的贪心】

缺乏、安全感 2022-08-12 08:59 150阅读 0赞

题目：[hdoj 5037 Frog][]

题意：一直聪明的青蛙，每次能条 l 的长度，河宽为m，喝中心有一些陆地，它会选择尽量少的次数跳，现在上帝可以任意往喝里面放陆地（视为点），让青蛙跳的次数最多，求最大次数？

分析：1：首先如果加入大于（l+1）的距离，那么上帝会给他分成（l+1）的段，因为我给他（l+1），它一下子跳不过去，必然中间还要一个点，让青蛙跳，这样肯定步数最大。（贪心策略）

2：贪心的时候以每一段剩余区间开始点作为贪心的开始点，假如它和后面区间的和大于等于（l+1）时，那么可以让它跳过前面的区间，否则让继续加。

这个题目比赛的时候整了三个小时没过，其实当时贪心策略是对的，当时只是保留了余数，但是没有从余数的前面算起（即区间初始点），后面wa了无数次之后，生成随机数找了一下，发现要从区间初始点开始。然后想到后面的要怎么处理，当时写的很复杂，没有调试出来。

中间特意化了一段时间确定是否是dp，否定了dp，可能是前一场人品用尽，这一场一道都不让过。

AC代码：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    typedef long long ll;
    using namespace std;
    
    const int maxn=200005;
    int a[maxn];
    
    int main()
    {
        int T;
        scanf("%d",&T);
        for(int cas=1;cas<=T;cas++)
        {
            int n,m,l;
            scanf("%d%d%d",&n,&m,&l);
            for(int i=1;i<=n;i++)
                scanf("%d",&a[i]);
            a[++n]=m;a[0]=0;
            int ans=0,k=l;
            sort(a,a+n+1);
            for(int i=1;i<=n;i++)
            {
                int x=(a[i]-a[i-1])%(l+1);
                int y=(a[i]-a[i-1])/(l+1);
                ans+=y*2;
                if(k+x>=l+1)
                    k=x,ans++;
                else
                    k=x+k;
            }
            printf("Case #%d: %d\n",cas,ans);
        }
        return 0;
    }

[hdoj 5037 Frog]: http://acm.hdu.edu.cn/showproblem.php?pid=5037