计蒜客-跳跃游戏(贪心)

链接如下:

跳跃游戏 - 题库 - 计蒜客 

给定一个非负整数数组，假定你的初始位置为数组第一个下标。数组中的每个元素代表你在那个位置能够跳跃的最大长度。请确认你是否能够跳跃到数组的最后一个下标。

例如：A=[2,3,1,1,4]A = [2,3,1,1,4]A=[2,3,1,1,4]能够跳跃到最后一个下标，输出true；

A=[3,2,1,0,4]A = [3,2,1,0,4]A=[3,2,1,0,4]不能跳跃到最后一个下标，输出false。

这道题提示是让用贪心算法,确实贪心更好用.关于贪心算法,不熟悉可以问度娘.

贪心,顾名思义是贪,这道题可以直接走最对于不同地方出发能走的最远.

当然前提是你能走到那一步.

---

#include<cstdio>

#include<algorithm>

using namespace std;

int main()

{

    int data[501];

    int n,i;

    scanf("%d",&n);

    for(i=0;i<n;i++)

        scanf("%d",&data[i]);

    int maxleap=0;  //最大走的距离

    for(i=0;i<n;i++){

        if(i<=maxleap)  //保证你可以走到那一步

        maxleap=max(maxleap,data[i]+i);  //在这一步能走出最远距离与之前能走出最远距离作比较.

        else break;  //如果不能再走了,即i>maxleap 跳出就行了.

    }

    if(maxleap>=n-1) printf("true");

    else printf("false");

    return 0;

}