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

跳跃游戏(三)

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")

全部评论

相关推荐

03-14 11:58
门头沟学院 Java
腾讯暑期实习java选手,完全不懂C++,貌似游戏行业都是用C++的而且天美好像在成都,个人比较想去上海或深圳
siestaaaaaa:天美不止在成都,深圳上海都有。 游戏服务器也不全是cpp,至少我们项目是java ,但是工作中什么语言都会用到,比如cpp、lua、py等等,语言本身其实不重要
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务