題干：

有一種跳躍游戲：假設初始位置在數軸的原點處，每一次可以選擇兩種操作： 向前k步或向后一步（k為當前的移動次數，即第k次跳躍k步）。給定一個終點D（D>0），請問最少經過多少次跳躍能恰好到達終點。（你可以跳到數軸的負半軸上）。

輸入格式:

輸入一個整數D（1≤D≤1018），代表終點。

輸出格式:

輸出一個整數，代表恰好到達D的最少的跳躍步數。

輸入樣例1:

在這里給出一組輸入。例如：

5

結尾無空行

輸出樣例1:

4

結尾無空行

hint: 0->1->3->6->5

輸入樣例2:

在這里給出一組輸入。例如：

6

結尾無空行

輸出樣例2:

3

結尾無空行

hint: 0->1->3->6

解題報告：

對于這種構造的題目，先別想著通過證明得出一個策略。最好的思路是先想策略，或者說猜一個策略，然后去證明這個策略是最優的。

本題猜的策略就是一直向前跑，挑一步往后跑。

猜這個策略的原因：簡單模擬下發現，如果一直往前跑，則肯定是最少的跳躍次數，但是有可能會跳過了?？紤]能不能再多用一步跳回來。發現是可以的。

詳細證明：如果都往前跳，則第i步的貢獻是i，如果第x步（x>0）向后跳了，則貢獻是-(x+1)，所以我們只需要挑選合適的x，就能做到了。x=0要特判，即代碼中sum-1=n的情況。

AC代碼：

#include<iostream> #include<cstring> #include<algorithm> #include<cmath> using namespace std; long long n; int main() {cin>>n;long long l = 1, r = 1e10, mid, ans, sum;while(l <= r) {mid = (l+r)/2;sum = mid*(mid+1)/2;if(sum >= n) {ans = mid;r = mid - 1;}else {l = mid + 1;}}sum = ans * (ans + 1) / 2;if(sum-1 == n) cout << ans+1 << endl;else cout << ans << endl;return 0; }

總結

以上是生活随笔為你收集整理的【思维构造】跳跃游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。