首页 > 代码库 > hdoj 5037 Frog 【万恶的贪心】

hdoj 5037 Frog 【万恶的贪心】

题目: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 【万恶的贪心】