题解 | 机器人跳跃问题

#include <iostream>
#include <vector>
#include <map>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>

using namespace std;
#define int long long

const int N = 1e5 + 4;
vector<int> vec;
int n;

//方法：二分答案（答案一定位于高度数组的最大值与最小值之间，具有单调性，所以可以采用二分答案）
//注意：在机器人跳跃的过程中，甚至可能出现 long 越界的情况，比如 长度为 1000 的 {1, ...., 1}能量初始值为 5 的情况，后面会累加2的幂次，结果很恐怖
//所以需要在 check函数中传入 max参数,用于比较剪枝：当处于某处其能量值大于整个高度数组的最大值的时候，这时候一定能通关，无需进行下一步判断，直接剪枝

bool check(int mid, int max)
{
    int e = mid;
    for (int i = 0; i < n; i++)
    {
        if (vec[i] > e) e -= (vec[i] - e);
        else e += (e - vec[i]);

        if (e < 0) return false;
        if(e >= max) return true;
    }
    return true;
}


signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    vec.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> vec[i];
    }
    int l = *min_element(vec.begin(), vec.end()), r = *max_element(vec.begin(), vec.end());
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid, *max_element(vec.begin(), vec.end()))) r = mid - 1;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}