HDU-5037 Frog (贪心)

传送门

思路：参考https://blog.csdn.net/qq_35781950/article/details/75207937

最优策略是跳两次前进l+1长度。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
/*尽可能的让青蛙多跳，。那就是如果那个青蛙
就是在他刚好跳过的第一个地方放石头，给他过

*/
const int maxn=200006;
int st[maxn];
int main()
{   int t;
    int m,n,l;
    scanf("%d",&t);
    for(int tt=1;tt<=t;tt++){
       scanf("%d%d%d",&m,&n,&l);
        for(int i=1;i<=m;i++)
            scanf("%d",&st[i]);
        st[0]=0;st[++m]=n;
        sort(st,st+m+1);
        int k=l;
        int ans=0;
          for(int i=0;i<=m;i++)
          {
            int x=(st[i]-st[i-1])%(l+1);
            int y=(st[i]-st[i-1])/(1+l);
            if(k+x>l)
            {
                ans+=2*y+1;
                k=x;
            }
            else
            {
                ans+=2*y;
                k+=x;
            }
        }
        printf("Case #%d: %d\n",tt,ans);
    }
    return 0;
}