题解 | 机器人跳跃问题 二分答案法

#include <iostream>
using namespace std;
int n,a[100005],l,r,ans,ma;
bool check(int m,int max){
    for(int i:a){
        if(m>=max)return true;//如果给的数据很大，那么后续能量增长将非常恐怖，
        if(m<i){              //一旦能量超过高度最大值，后面肯定通关了，可以提前返回了
            m-=i-m;
            if(m<0)return false;
        }
        else m+=m-i;
    }
    return true;
}
int main() {
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        ma=max(ma,a[i]);
    }
    r=ma;//确定答案范围
    while(l<=r){
        int m=(l+r)/2;
        if(check(m,ma)){
            ans=m;
            r=m-1;
        }
        else l=m+1;
    }
    cout<<ans;
}

第3题【算法讲解051【必备】二分答案法与相关题目】 https://www.bilibili.com/video/BV1Mh4y1P7qE/?share_source=copy_web&vd_source=5065fa61022691e8df35c771a30e6d29