acwing730. 机器人跳跃问题

题目

题解

如果H[k+1]>e,那么e=e-(h[k+1]-e)
如果h[k+1]<e,那么e=e+(e-h[k+1))
所以不管大于还是小鱼，e=2*e-h[k+1]
对于初始的e，如果e满足条件那么，比e大的初始值肯定也能满足条件，由此想到二分法

#include<iostream>
using namespace std;
const int N=1e5+10;
int n,h[N];
bool check(int e){
    for(int i=1;i<=n;i++){
        e=e*2-h[i];
        if(e>=1e5)return true;
        if(e<0)return false; 
    }
    return true;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&h[i]);
    }   
    int l=0,r=1e6+10;
    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<l<<endl;
    return 0;
}