题解 | #跳跃游戏(三)#
跳跃游戏(三)
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")