鏈接如下:

跳躍游戲 - 題庫 - 計(jì)蒜客?

給定一個(gè)非負(fù)整數(shù)數(shù)組，假定你的初始位置為數(shù)組第一個(gè)下標(biāo)。數(shù)組中的每個(gè)元素代表你在那個(gè)位置能夠跳躍的最大長度。請確認(rèn)你是否能夠跳躍到數(shù)組的最后一個(gè)下標(biāo)。

例如：A=[2,3,1,1,4]A = [2,3,1,1,4]A=[2,3,1,1,4]能夠跳躍到最后一個(gè)下標(biāo)，輸出true；

A=[3,2,1,0,4]A = [3,2,1,0,4]A=[3,2,1,0,4]不能跳躍到最后一個(gè)下標(biāo)，輸出false。

這道題提示是讓用貪心算法,確實(shí)貪心更好用.關(guān)于貪心算法,不熟悉可以問度娘.

貪心,顧名思義是貪,這道題可以直接走最對于不同地方出發(fā)能走的最遠(yuǎn).

當(dāng)然前提是你能走到那一步.

#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);? //在這一步能走出最遠(yuǎn)距離與之前能走出最遠(yuǎn)距離作比較.

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

? ? }

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

? ? else printf("false");

? ? return 0;

}