Acwing 730. 机器人跳跃问题

Acwing 730. 机器人跳跃问题

思路：
首先看递推式：一共有三种情况，我们可以发现对于一个位置x, 每个x处的位置三种情况下的剩余能量都是以下。

对于一般式：e = 2 * e - H[k + 1] 可以发现，当e增大的时候，e也会增大，所以可以使用二分查找去查找e，问题来到左右边界的选择。

首先左边界很容易可以选出为0，右边界的问题：我们假设每个点的h[x + 1]都为y，起始能力量也为y，则第一次是 y = 2 * y - y = y > 0,如果把每个点的前端看出起始位置，则右边界选为y一定不会出现丢失答案的情况。所以我们可以选择最大值为右边界，即0 < N < 100000,右边界为 100000

代码：

#include<iostream>
using namespace std;
const int N = 1e5;
int nums[N];
int n;
bool check(int x){
    for(int i = 0; i < n; i++){
        x = x * 2 - nums[i];
        if(x > N) return true;
        if(x < 0) return false;
    }
    return true;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> nums[i];
    
    int l = 0, r = N;
    while(l < r){
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
    return 0;
}