时间复杂度O(n*logn)

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
int high[N];  //每个塔的高度
int n;
//要求一个最小的能量使得机器人可以跳到最后一个位置
//如果h(k+1) > E 则能量的变化为 E = E - h(k+1) +E = 2E - h(k + 1)
//如果h(k+1) <= E 则能量的变化为 E = E + E - h(k+1) = 2E-h(k+1)
//所以不管什么情况能量的变化都是一个式子
//很显然如果有能量大于等于我们要求的ans，则机器人一定可以跳到最后一个
//why?
//如果我们要求的ans可以使得机器人跳到最后一个位置，则可以知道到达每个位置的能量一定大于等于0
//现在有一个能量大于ans  E0' > E0
//则E1' = 2E0' - h(1) > 2E0 - h(1) == E1
//所以可以得到E1'大于等于0 以此类推，所以大于ans一定可以跳到最后一个位置
//小于ans就不能跳到最后一个位置，所以可以用二分找这个ans
bool check(int e , int MaxH){
    for (int i = 1;i <= n;i++){
        e = 2 * e - high[i];
        if (e >= MaxH) return true;
        if(e < 0) return false;
    }
    return true;
}
int main (){
    cin >> n;
    int MaxH = -1e9;
    //很显然能量不会超过最大的高度
    //因为如果能量大于最大的高度 E > MaxH
    //则E1 = 2E0 - h(k+1) = E0 + MaxH - h(k+1) 
    //很明显MaxH-h(k+1) 一定是大于等于0的 则这个E = E0 + (大于等于0)一定是单调调增的
    //所以大于MaxH的能量是一定可以的
    for (int i = 1;i <= n;i++){
        scanf ("%d" , &high[i]);
        MaxH = max(MaxH , high[i]);
    }
    //二分左端点
    int l = 1;
    int r = MaxH;
    while(l < r){
        int mid = l + r >> 1;
        //cout << mid << endl;
        if (check(mid , MaxH)){  //说明这个能量可以
            r = mid;
        }
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}