贪心算法：FROG

不得不说技术不到位到哪里都是有难度的，本来挺简单的一道题，结果仍然没有AC。
题意如下：一只青蛙想要过一条宽M的河，他一次只能最多挑L，河里有N块石头，你是上帝，会添加无限制数量的石头来帮助它过河，但你想让它尽量跳很多次，但是聪明的青蛙会选择跳上在跳远范围内最远的那块石头。
接下来开始分析：
在河上已经有一定数量的石头时，你会想尽一切办法让青蛙来跳更多的次数。

你可能会想，在已知两块石头中间添加一块石头让青蛙跳上去，那样就会它就多跳一次了 但是想清楚啦，当开始两块石头的距离在L之内的话它是不会多跳这一步的，所以当两块石头的间距等于小于L时你添加石头的方法是行不通的，甚至会减小青蛙的步数：

那么应该怎样让它多跳步数呢？你又想到了另外一种方法，当这个青蛙在跳到最后一块石头，即下一块石头它跳不到了的时候你再安放石块，那样，青蛙就可以跳你安放的石块了。

你可能会想到，在接下来仅有的一个L距离上，放置一个石块，在距离原始位置Ｌ＋１处再放置一块，那么将会是在最短距离内跳最多次数的方案了。

但是你没想到，当放置的石块距离不当时也青蛙还是会少走一步：

所以你总结出了规律：
从青蛙所在起点开始，如果现有的石块间距可以达到Ｌ，那么青蛙一定会选择目前距离它最远且在Ｌ之内的石块来跳跃，青蛙每跳一次则会将跳跃步数加一，也不存在增加步数的情况。
当目前青蛙的所站的石块前方没有可以跳跃的原先石块时，你会把石块放在距离当前的石块之前的石块Ｌ＋１的位置，因为这样最有可能达到你的目的。

这样就可以总结算法了，从第一块石头开始，只要测量两块石头之间的距离，这两块石头的距离加上上一步的距离小于等于L，那么就可以合并步数，和设为上一步的步数，步数不变。之后大于L的没有任何石块的情况，则可以每L+1距离并未两步。

即当上一步与（L+1）剩余部分的和大于L+1时，需要将步数加上一，否则，合并步数，不加一。
当分析完以后，你就可以回家编写程序来应对所有的青蛙过所有不同的河的情况了。
所以你写了如下的代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

const int maxn = 200010;
int a[maxn];
int main()
{
    int T,N,M,L,p,ans=0,last,now=0,j,i;
    scanf("%d",&T);
    for(int hu = 1; hu <= T; hu++)
    {
       scanf("%d%d%d",&N,&M,&L);
       for(int k = 1; k <= N; k++)
       scanf("%d",&a[k]);
       a[0]=0;
       a[++N]=M;
       sort(a,a+N);
       j=0;
       ans=0;
       j=L;//第一步的特殊情况，使下一步的余（L+1）部分（小于L+1的部分），都可以直接作为上一步，机满足第二种情况，所以初始化为L
       for (i=1;i<=N;i++)
       {
            now=(a[i]-a[i-1])%(L+1);
            last=(a[i]-a[i-1])/(L+1);
            if (j+now>=(L+1))
            {
                j=now;
                ans+=2*last+1;
            }
            else 
            {
                j=j+now;
                ans+=2*last;
            }
       }
        printf("Case #%d: %d\n",hu,ans);
    }
    return 0;
}

在线提交了一下，居然ＡＣ了，相信你一定很高兴O(∩_∩)O