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

#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define sec second
#define eb emplace_back
#define pb push_back
#define all(x) x.begin(), x.end()
#define all_(x) x.begin() + 1, x.end()
#define rall(x) x.rbegin(), x.rend()
#define rall_(x) x.rbegin(), x.rend() - 1

using namespace std;
using ll = long long;
using LL = __int128;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using pii = pair<int, int>;

const int INF = 0x3f3f3f3f;
const int p = 998244353;
const int mod = 1e9 + 7;

ll sqrt_f(const ll &x) {ll l=0,r=INF;while(l+1^r){ll mid=l+r>>1;(x<mid*mid?r:l)=mid;}return l;}
ll sqrt_c(const ll &x) {ll l=-1,r=INF;while(l+1^r){ll mid=l+r>>1;(mid*mid<x?l:r)=mid;}return r;}
int gcd(int a, int b) {return b?gcd(b,a%b):a;}

istream &operator>>(istream &is, LL &x) {string a;is>>a;bool k=a[0]=='-';if(k)a=a.substr(1);x=0;for(char &c:a)x=x*10+c-48;if(k)x=-x;return is;}
ostream &operator<<(ostream &os, LL x) {if(x<0)os<<'-';x=-x;string a;do a+=x%10|48;while(x/=10);reverse(all(a));return os;}
template<typename U, typename V>U qpow(U x, V n){U y(1);while(n){if(n&1)y*=x;x*=x;n>>=1;}return y;}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n; cin >> n;
    vi vt(n);
    for(int &x : vt) cin >> x;
    ll l = 0, r = *max_element(all(vt));
    ll m = r;
	// 左右开区间写法
    auto check = [&](ll start) -> bool {
        for(int &x : vt) {
            start += start - x;
            if(start < 0) return false;
            else if(start >= m) return true;
        }
        return true;
    };
	// 二分答案
    while(r > l + 1) {
        ll mid = (l + r) >> 1;
        ((check(mid)) ? r : l) = mid;
    }

    cout << r << endl;
	return 0;
}