C++機器人跳躍問題（二分搜尋）

機器人正在玩一個古老的基於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)≤105,
輸入樣例1：
5
3 4 3 2 4
輸出樣例1：
4
輸入樣例2：
3
4 4 4
輸出樣例2：
4
輸入樣例3：
3
1 6 4
輸出樣例3：
3

AC程式碼：

#include<stdio.h>
#include<algorithm>

using namespace std;

int n;
int h[100010];
int backup[100010];//資料備份
int ans=0x7f7f7f7f;

bool check(int e)
{
    long long int E=e;
    bool flag=true;
    for(int i=0;i<n;++i)
    {
        if(h[i+1]>E) E-=h[i+1]-E;
        else E+=E-h[i+1];
        if(E<0){flag=false;break;}
        //可以發現，每次E的新值都為2E-h[i+1]
        //當E>=最大柱子高度
        //E只增不降，不必再往下判斷
        if(E>=backup[n]) break;
    }
    return flag;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&h[i]);
        backup[i]=h[i];
    }
    sort(backup+1,backup+n+1);//求最大柱子高度
    int l,r,mid;
    l=0;//左開右開區間
    r=backup[n]+1;
    while(l+1!=r)
    {
        mid=l+((r-l)>>1);
        if(check(mid)){//滿足就繼續探索更小的可能
            r=mid;
            ans=min(ans,mid);
        }
        else l=mid;//不滿足只能往更大的去
    }
    printf("%d",ans);
    return 0;
}