本文主要是介绍4.3 传送门,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
算法设计与分析 4.3 传送门
题目描述
现在有 n 个传送门,你处在第一个传送门的位置,第 i 个传送门可以将你传送到第 i-a[i] 到第 i+a[i] 范围内的任意一个传送门,请问你最少需要几次操作,使得你可以传送到最后一个传送门的位置。
保证题目一定有解。
输入格式
第一行为一个正整数 n( 1 <= n <= 104 )
第二行 n 个整数 a[i](0 <= a[i]<=1000)
输出格式
输出一个整数,表示最少操作次数。
样例输入
5
2 3 1 1 4
样例输出
2
参考代码
#include <stdio.h>
/*
* 判断当前i+a[i]是否可以到达n-1的位置,可以则结束;
* 否则寻找i+1到i+a[i]范围内的最大值(j+a[j]);
* 然后i跳到j
* 重复
* 时间O(n)
*/
int main()
{//FILE* s;//freopen_s(&s,"5.txt", "r", stdin);int n, count = 0;scanf("%d", &n);int a[10001];for (int i = 0; i < n; i++){scanf("%d", &a[i]);}int i = 0, len = a[0], max;while (i<n-1) {max = 0;len = i + a[i];if (len >= n - 1) {count++;break;}for (int j = i + 1; j <= len; j++) {if (j + a[j] > max) {max = j + a[j];i = j;}}count++;}printf("%d", count);
}
这篇关于4.3 传送门的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!