您现在的位置是:首页 > 正文

4.3 传送门

2023-11-06 15:37:19阅读 350

算法设计与分析 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);
}
文章来源:https://blog.csdn.net/yyh520025/article/details/134233149
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:https://www.dflian.com/995.html

网站文章