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

个人思路:二分答案算法
该题具有单调性如所剩能量以及跳入下一个建筑的能量比较
故可以采用二分算法进行解决

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200050;
ll a[N],n,mx,r,l,sum;

bool f(int energy,int max){
      for(int i=0;i<n;i++){
        if(energy<=a[i]){
            energy-=a[i]-energy;
        }
       else {
         energy+=energy-a[i];
       }
       if(energy>=max){
        return true;
       }
       if(energy<0){
return false;
       }
       }
       return true;
      }
void solve(){
      l=0,r=mx;ll ans=-1;
      while(l<=r){
        ll m=l+(r-l)/2;
        if(f(m,mx)){
ans=m;r=m-1;
        }
        else {
        l=m+1;
        }

      }
cout<<ans<<endl;

}
int main(){
    int t=1;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];mx=max(mx,a[i]);
    }

    while(t--){
        solve();
    }
}