機器人跳躍問題

思路

給定一個數組nums代表高度，機器人會有一個初始能量 $E$ ，從第一個位置開始出發，
如果大於目標高度，機器人獲得E - nums[i]的能量，否則機器人消耗nums[i] - E，
要求找到一個最低的初始能量，能讓機器人走到尾端。

假如現在 $nums=[1,5,3]$ ，機器人初始能量 $3$ 。

• 第一個位置，獲得 3 - 1 = 2 的能量，當前能量來到 5。
• 第二個位置，消耗 5 - 5 = 0 的能量，能量保持為 5。
• 第三個位置，獲得 5 - 3 = 2 的能量，最終能量來到 7。

1. 直接找到目標的能量很難。
2. 初始能量越大，機器人就越有可能來到結尾位置。

根據前兩點，可以二分答案，假如當前設定的初始能量 $x$ 能到結尾，
那麼 $\geq{x}$ 的初始能量都能來到結尾，不需要驗證。
對於機器人來說，最糟糕的情況就是第一步就需要大量的能量，這個能量就是nums當中的最大值 $\max(nums)$ 。
反過來說，假如現在的能量已經 $\geq\max(nums)$ ，後續總體都是在獲取能量，可以提前回傳答案。
如果不提前回傳，能量的數值可能會溢出。
設 $x=10^5$ ， $nums=[1,1,\dots]$ ，能量的變化會是

• $x = 10^5+10^5-1\approx10^6$
• $x=10^6+10^6-1\approx10^7$
• $\dots$

當數組長度太大，能量就會溢出。

程式碼

二分搜索

#include <iostream>
#include <array>
using namespace std;

const int MX = 1e5+1;
array<int, MX> nums;
int n, mx;
bool check(int energy) {
    for(int i = 0; i < n; i++) {
        if(nums[i] > energy) { // 高度比較高，消耗能量
            energy -= (nums[i] - energy);
        }
        else { // 高度比較低，獲取能量
            energy += (energy - nums[i]);
        }
        if(energy >= mx) return true; // 能量 >= mx, 必定通關
        else if(energy < 0) return false; // 來到負數，失敗
    }
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    mx = 0;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> nums[i];
        mx = max(mx, nums[i]);
    }
    int left = 0, right = mx + 1; // 如果初始能量 >= mx, 就直接通關了，
    while(left + 1 < right) { // 開區間二分
        int mid = left + (right - left) / 2;
        (check(mid) ? right : left) = mid;
    }
    cout << right;
}

複雜度分析

• 時間複雜度：$O(n\log(\max(nums)))$
• 空間複雜度：$O(n)$