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

采用贪心策略，从a[0]开始,每次跳之前判断当前点能跳到的点中哪个点能跳得更远，然后跳到那个点。如果当前点能直接跳到a[n-1]，则跳一步结束循环；如果当前点能跳到的每个点都不能比当前点跳得更远，GG，说明跳不到a[n-1]。n<=1e5,m<1e3,时间复杂度为O(mn)，不会超时。

int main() {
    int n, a[100010], step = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
    }
    if(n==1){printf("0");return 0;}//只有一个数，不用跳，就到达终点
    int i = 0;
    while (true) {
        if (i + a[i] >= n - 1) {//能直接跳到终点
            step++;
            break;
        }
        int pos = i;
        for (int j = i + 1; j <= i + a[i]; j++) {
            if (j + a[j] > pos + a[pos])pos = j;
        }
        if (pos == i) {//能跳到的点不能比a[i]跳得更远，跳不到终点
            step = 0;
            break;
        } else {//跳到能跳最远的点
            i = pos;
            step++;
        }
    }
    printf("%d", step ? step : -1);
}
// 64 位输出请用 printf("%lld")