analyse

• 找到满足条件judge(x)的最小x问题，即最优化问题，二分法解决。
• 坑：题目描述“如果 H(k+1)>E，那么机器人就失去 H(k+1)−E 的能量值，否则它将得到 E−H(k+1) 的能量值，”，代码实现：每次E都更新为2E-H(k+1)，E是指数增加，随随便便就越界，所以不能走到第N个再判断是否成功。
• 只要当前E不小于的最大H就是成功。

code

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1e5+5;
int h[N];
bool pass[N];
int n;


int find_max() {

    int mmax = h[0];
    for(int i = 0; i < n; i++) {
        if(h[i] > mmax)
            mmax = h[i];
    }
    return mmax;
}

bool judge(long long x, int max_h) {
    for(int i = 0; i < n; i++){
        x = 2*x-h[i]; // x可能溢出 !!!
        if(x >= max_h)
            break;
        if(x < 0 )
            return false;
    }
    return true;
}

int main(int argc, char** argv) {
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> h[i];
    }
    int low = 0 ;
    int up = N;
    int max_h = find_max();
    while(low < up) {
        int mid = low+up >> 1;
        if(judge(mid, max_h)) 
            up = mid;
        else 
            low = mid+1;
    }
    cout << up << endl;
    return 0;
}