题解 | #机器人跳跃问题#

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

const int MAXN = 100001;
int arr[MAXN];
int n;

bool f(int energe, int max){
    for(int i = 1; i <= n; i++){
        if(energe <= arr[i]){
            energe -= arr[i] - energe;
        }else{
            energe += energe - arr[i];
        }
        if(energe >= max){
            return true;
        }
        if(energe < 0){
            return false;
        }
    }
    return true;
}

int compute(int l, int r, int max){
    int m , ans = -1;
    while(l <= r){
        m = l + ((r - l) >> 1);
        if(f(m, max)){
            ans = m;
            r = m - 1;
        }else{
            l = m + 1;
        }
    }
    return ans;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    while(cin >> n){
        int l = 0, r = 0;
        for(int i = 1; i <= n; i++){
            cin >> arr[i];
            r = max(r, arr[i]);
        }
        cout << compute(l, r, r) << endl;
    }
    return 0;
}