题解 | 跳跃游戏(三)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    if (n <= 1) {
        cout << 0 << '\n';
        return 0;
    }

    int steps = 0, end = 0, far = 0;
    for (int i = 0; i < n - 1; ++i) {
        if (i > far) {                // 已经跳不到当前位置了
            cout << -1 << '\n';
            return 0;
        }
        far = max(far, i + a[i]);     // 下一跳的最远可达
        if (i == end) {               // 需要进行一次跳跃，扩展区间
            ++steps;
            end = far;
            if (end >= n - 1) break;  // 已覆盖终点
        }
    }
    cout << (end >= n - 1 ? steps : -1) << '\n';
    return 0;
}