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

跳跃游戏(三)

https://www.nowcoder.com/practice/d92a70f4f42248d688b93c9e50d2e757

采用贪心策略,从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")

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务