HDU Frog
这里是一篇题解转载：讲的很清楚
转自：https://blog.****.net/u014569598/article/details/39471913
分析：贪心吧，让三个石头第一个和第三个距离为L+1，并让每次跳的点尽量小，即尽可能多的给出0，x,L+1这样的石头相对位置，且使x尽量小，x的最小位置取决于前面一步的限制（不要和x前一石头以前任何石头距离小于等于L，否则x前一石头就会被跳过）。
石头是可能无序的，比赛是实在没发现，就加了个排序过了，哎。。。
和代码一起讲做法吧，假设情况1 ：上一步k加这一步余数x大于L，则最后剩余部分需要单独跳；情况2：上一步k加这一步余数x小于等于L，最后剩余部分可以并进上一步，即k+x。
画了一张图；
代码：
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<cmath>
- #include<algorithm>
- #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<l+1)
- {
- k=x+k;
- ans+=y*2;
- }
- }
- printf("Case #%d: %d\n",++cas,ans);
- }
- return 0;
- }