题解 | #跳跃游戏(三)#

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

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

        vector<int> ans; // 存储下标：跳几次到最后，存储值：位置下标
        ans.push_back(n-1);

        // 从倒第二位置 往前遍历，
        for (int i = n - 2; i >= 0; --i) {
            if (i + a[i] >= ans.back()) {  // 可以跳到最近的可达点
                while(ans.size() > 1) {  // 可以尝试跳的更远
                    int try_steps = ans.size() - 2;
                    int try_pos = ans[try_steps];
                    if(i + a[i] >= try_pos) {  // 尝试成功
                        ans.pop_back();  // 最近的可达点 可 删除了
                    }
                    else {
                        break; // 尝试失败，不用再尝试了
                    }
                }
                ans.push_back(i);  // 记录最近的可达点
            }
        }

        if(ans.back() == 0) {
            cout << ans.size() - 1 << endl;
        }
        else {
            cout << -1 << endl;
        }
    }
}
// 64 位输出请用 printf("%lld")