[数据结构与算法]Acwing第730题(机器人跳跃问题)

相关题目：

相关代码：

(贪心做法)

/*
    假设刚好到了最后的时候，能量为0。
*/
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int num[N];
int n;
int E[100010];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>num[i];
        for(int i = n ; i >= 1;i--){
               E[i-1] = (num[i] + E[i]+1) / 2;
        }
    cout<<E[0]<<endl;
}

?

?

(二分做法)

#include<iostream>
using namespace std;
int a[100001];
int N;
bool check(int mid){
    for(int i=1;i<N+1;i++){
        mid=mid*2-a[i];
        if(mid<0){
            return false;
        }
        if(mid>1e5){
            return true;
        }
    }
    return true;
}
int main(){
    cin>>N;
    for(int i=1;i<=N;i++){
        cin>>a[i];
    }
    int l=0,r=1e5+1;
    while(l<r){
        int mid=(l+r)/2;
        if(check(mid)){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    cout<<l<<endl;
    return 0;
}