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

「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int nums[N];
int n;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    //初始化最远位置标记far
    int far = nums[0];
    int ans = 1;
    if (n == 1)
        printf("0");
    else {
        for (int i = 0; i < n; i++) {
            int tmpi = i;
            int tmp = 0;
            // 在(i,far] 中找能到达的最远位置
            for (int j = i + 1; j <= far; j++) {
                if (nums[j] + j > tmp) {
                    tmp = nums[j] + j;
                    tmpi = j;
                }
            }
            //在范围内没找到，说明到达不到最后，跳出循环
            if (tmpi == i) {
                break;
            } else  // 次数加1
                ans ++;
            far = tmp;  // 更新最远位置
            if (far >= n - 1)// 如果最远位置 可以到达最后的位置，跳出循环
                break;
            i = tmpi - 1;  // 最后更新下次循环的起始位置，i=tmpi-1，for里面还有+1，所以下一次的遍历起始位置是tmpi,就是本次找到的最远位置的起跳位置
        }
        if (far >= n - 1)
            printf("%d", ans);
        else
            printf("-1");
    }

    return 0;
}
// 64 位输出请用 printf("%lld")