機器人正在玩一個古老的基于DOS的游戲。

游戲中有N+1座建筑——從0到N編號，從左到右排列。

編號為0的建筑高度為0個單位，編號為 i 的建筑高度為H(i)個單位。

起初，機器人在編號為0的建筑處。

每一步，它跳到下一個（右邊）建筑。

假設機器人在第k個建筑，且它現在的能量值是E，下一步它將跳到第k+1個建筑。

如果H(k+1)>E，那么機器人就失去H(k+1)-E的能量值，否則它將得到E-H(k+1)的能量值。

游戲目標是到達第N個建筑，在這個過程中能量值不能為負數個單位。

現在的問題是機器人至少以多少能量值開始游戲，才可以保證成功完成游戲？

輸入格式
第一行輸入整數N。

第二行是N個空格分隔的整數，H(1),H(2),…,H(N)代表建筑物的高度。

輸出格式
輸出一個整數，表示所需的最少單位的初始能量值上取整后的結果。

數據范圍
1≤N,H(i)≤10^5,

輸入樣例1：
5
3 4 3 2 4
輸出樣例1：
4
輸入樣例2：
3
4 4 4
輸出樣例2：
4
輸入樣例3：
3
1 6 4
輸出樣例3：
3

代碼如下：

#include <iostream> using namespace std; const int N = 1e5; int w[N]; int n; bool check(int mid) {for (int i = 0;i<n;i++){mid = 2*mid-w[i];if (mid > 1e5) return true;if (mid < 0) return false;}return true; }int main() {cin>>n;for (int i = 0;i<n;i++) cin>>w[i];int l = 1,r = 1e5;while(l < r){int mid = l+r>>1;if (check(mid)){r = mid;}else{l = mid+1;}}cout<<r<<endl; }

總結

以上是生活随笔為你收集整理的AcWing 730. 机器人跳跃问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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