题解 | 跳跃游戏(一)

#include <iostream>
using namespace std;

const int N = 200010;
int n, a[N], d[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    d[1] = 1, d[2] = -1;
    for (int i = 1; i <= n; i++) {
        int l = i + 1, r = i + a[i];
        if (r < l) continue;
        d[l] += 1;
        if (r <= n) d[r + 1] -= 1;
    }
    int s = 0;
    for (int i = 1; i <= n; i++) {
        s += d[i];
        if (s <= 0) {
            cout << "false";
            return 0;
        }
    }
    cout << "true";
    return 0;
}
// 64 位输出请用 printf("%lld")

差分解法。遍历1-n的位置，遍历到第i个位置时，区间[i + 1, i + a[i]]的所有值都加上1。最后算每个位置的累加值，如果位置i的累加值为0，说明从前面位置不可能跳到i，直接输出false即可（因为跳不到i，就不可能跳到后续位置）。如果累加值一直大于0，说明能跳到最后，输出true。