7-15 跳一跳

7-15 跳一跳

Drizzle 面前有一条由一堆非负整数组成的道路，从第一个数字起步，每次他都能跳出不大于当前数字的距离，每个数字之间的距离为1，那么他最少需要跳多少次才能到达终点？

要求:

输入：第一行输入道路中数字的个数n也就是道路的长度，第二行输入这n个数字

输出：输出一个数字，表示最少跳跃次数

输入:

5
2 3 1 1 4

输出:

2

解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

范围:

对于 20% 的数据：n≤100
对于 100% 的数据：n≤1000000
所有整数元素在int范围内

思路： 先在能到达距离内寻找到最大值，然后再在最大值于距离内找

代码如下：

#include
using namespace std;
const int Max = 1e6+10;
int a[Max];
int find(int n, int m){
	int ans = n+1;
	for(int i = n; i <= m; i ++){
		if(a[n] < a[i]){
			a[n] = a[i];
			ans = i;
		}
	}
	return ans;
}
int link(int n, int m){
	int ans = n;
	for(int i = ans; i <= m; i ++){
		if(a[n] < a[i]+(i-n)){
			n = i;
		}
	}
	return n;
}
int main()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i ++){
		cin >> a[i];
	}
	int k = 0, tmp = 1; // 最少跳一次
	while(k+a[k] < n-1){
        int p = a[k]; // 防丢失
		int m = find(k,a[k]+k); // 寻找k到a[k]+k之内最大值所在的位置
		k = link(m,p+k); // 寻找要跳入的位置上
		tmp ++;
	}
	cout << tmp << endl;
}