開始就覺得有思路，結果越敲越麻煩。。。?
題意很簡單，就是說一個青蛙從0點跳到m點，最多可以跳l的長度，原有石頭n個（都僅表示一個點）。但是可能跳不過去，所以你是上帝，可以隨便在哪兒添加石頭，你的策略是讓青蛙跳過去的次數最多，但是你添加了石頭后，青蛙會選擇最少的次數跳過去，問青蛙跳的次數最多是多少。
?
原有石頭與現在的距離不大于l，就找最遠的那個可以跳的石頭跳過去。接下來就是主要解決現在的位置與接下來的一塊石頭的距離大于l的情況了。模擬：上帝開始放石頭，要讓青蛙一定是這次跳這塊石頭（在上次不能跳），并且跳最近的距離。則它前一個位置 +l+1 與現在的位置 +1的最大值就是放石頭的位置。但是數據范圍太大，純模擬會超時，這時就要注意到每兩次放石頭后跳的距離會重復，最短的距離就是 l+1，但是這兒要特殊處理一下當某一次添加石頭后，它就可以直接跳到后面原有石頭上了（距離不大于l）。還有就是我的代碼需要特判還沒有跳出來在0的時候的情況，具體可以看代碼。
?
代碼寫得很麻煩
?
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; #define eps 1E-8 /*注意可能會有輸出-0.000*/ #define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x為兩個浮點數差的比較,注意返回整型 #define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮點數轉化 #define zero(x) (((x)>0?(x):-(x))<eps)//判斷是否等于0 #define mul(a,b) (a<<b) #define dir(a,b) (a>>b) typedef long long ll; typedef unsigned long long ull; const int Inf=1<<28; const double Pi=acos(-1.0); const int Max=200010; int rock[Max]; int n,m,l; int Solve() {int manx=0,now=0,pre=0;//最大步數 現在位置 前一個位置sort(rock,rock+n);rock[n++]=m;//添加最后一個石頭int ran,tmp,tmpp;for(int i=0;now<m;i++){if(i==n)i=n-1;if(rock[i]-now>l)//相差大于步數 l {if(i&&rock[i-1]-now<l&&rock[i-1]>now)//現在的位置最遠可以跳那個原有的石頭 {manx++;pre=now;now=rock[i-1];}if(rock[i]-now>l)//現在位置與之后的第一個原有石頭大于步數 l {ran=rock[i]-l-1;//如果運用上帝鋪的石頭跳到了這個位置后 可能再再跳一步或者兩步就可以直接跳到原有石頭tmp=(ran-now)/(l+1);//注意上帝鋪的石頭跳兩步一定最少跳過l+1的距離if(tmp){manx+=tmp*2;tmpp=now-pre;now+=tmp*(l+1);if(tmpp)pre=now-tmpp;//相差位置不變else//特判開始pre=now-l;}manx++;//現在一定可以在跳一次if(now){tmpp=now;now=max(now+1,pre+l+1);//上帝鋪的石頭使這一次可以跳到的最近距離pre=tmpp;}else//特判開始now=1;if(now+l>=rock[i]);//一步跳入與原有石頭距離不大于步數 l，就可以跳到現在這個原有石頭后者之后的原有石頭else//要再鋪一個石頭 {manx++;tmpp=now;now=max(now+1,pre+l+1);pre=tmpp;}}}if(rock[i]-now==l)//可能是上一個if遺留的 {pre=now;now+=l;manx++;}if(i==n-1&&rock[i]-now<l&&rock[i]>now){manx++;return manx;}}return manx; } int main() {int t,coun=0;scanf("%d",&t);while(t--){scanf("%d %d %d",&n,&m,&l);for(int i=0; i<n; i++)scanf("%d",&rock[i]);printf("Case #%d: %d\n",++coun,Solve());}return 0; }
?
