CPP-SUNUOJ-Problem P28. [算法课贪心] 跳跃游戏2

Problem P28. [算法课贪心] 跳跃游戏
有一个非负整数数组 nums ，最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

假设你总是可以到达数组的最后一个位置, 你的目标是使用最少的跳跃次数到达数组的最后一个位置。

输入

第一行输入一个整数n (1≤n≤10000) 代表数组的长度。

第二行输入一行数字代表数组 nums (0≤numsi≤1000)，数字与数字之间用空格间开。

输出

输出最少跳跃次数。

样例

标准输入
5
2 3 1 1 4
标准输出
2
标准输入
5
2 3 0 1 4
标准输出
2
标准输入
4
1 1 1 2
标准输出
3

参考文章

#include <iostream>
#include <bits/stdc++.h>
using namespace std;


int main()
{
    int n;
    cin >> n;
    int d;
    vector<int> nums;
    while(cin >> d)
    {
        nums.push_back(d);
    }
    int maxidx = 0;//记录最大和的位置
    int end = 0;//每搜索完一层，更新end=maxidx
    int cnt = 0;//记录跳跃次数

    for(int i=0; i<n-1; i++)//遍历数组，最后一个数字不需要遍历，因为要跳到最后一个数字位置上
    {
        //默认都可以跳到最后一个的前提下进行
        if(maxidx >= i) //可以跳跃到的最大位置一定要>=当前位置
        {
            maxidx = max(maxidx, i+nums[i]);
            if(i == end)//如果跳到这一层的末尾，则完成一次最大跳跃，cnt++；
            {
                cnt++;
                end = maxidx;
            }
        }
    }
    cout << cnt;
//    cout << "Hello world!" << endl;
    return 0;
}

自我练习，二刷

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/*
思路：此题目建立的前提是都可以跳跃到最后一位；不然直接输出cnt，其初始值也为0；
    定义maxidx为跳跃的最大位置；end最大位置末尾，用来进行cnt++，统计最大的跳跃步幅次数；初始值均为0；
    遍历数组，最后一个数字不需要遍历
        当前位置i要在最大跳跃位置内部；
            更新最大位置maxidx；与i+nums[i]进行比较；
            如果i位置恰好是最大跳跃位置末尾end，即是完美跳跃，即跳跃次数最少，步幅大；
                进行计数cnt++；
                更新下次跳跃末尾end=当前可以最大跳跃位置；

*/
int maxidx, en, cnt;//初始值均为0；这里不能用end，会ambiguous，有冲突，用en代替


int main()
{
    int n;
    cin >> n;//有多少个数字
    vector<int> nums;
    int x;
    while(cin >> x)
    {
        nums.push_back(x);
    }
    for(int i=0; i<n-1; i++)
    {
        if(i <= maxidx)
        {
            maxidx = max(maxidx, i+nums[i]);
            if(i == en)
            {
                cnt++;
                en = maxidx;
            }
        }
    }
    cout << cnt;
//    cout << "Hello world!" << endl;
    return 0;
}