hdu 5037 Frog（贪心） - c++编程基础

分析：贪心吧，让每次跳的点尽量小。

石头是可能无序的，比赛是实在没发现，就加了个排序过了，哎。。。

和代码一起讲做法吧，假设情况1 ：上一步k加这一步余数x大于L，则最后剩余部分需要单独跳；情况2：上一步k加这一步余数x小于等于L，最后剩余部分可以并进上一步，即k+x。

画了一张图；

代码：

#include
  
   
#include
   
     #include
     #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #define MOD 1000000007 typedef long long ll; using namespace std; const int maxn=200005; int da[maxn]; int main() { int T,n,m,l,cas=0; scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&l); for(int i=1;i<=n;i++) scanf("%d",&da[i]); da[++n]=m;da[0]=0; int ans=0; int k=l;//k表示上次跳的距离，用此限制下次的跳越 sort(da,da+n); for(int i=1;i<=n;i++) { int x=(da[i]-da[i-1])%(l+1); int y=(da[i]-da[i-1])/(l+1); if(k+x>=l+1) { k=x; ans+=y*2+1; } else if(k+x