题解 | 跳跃游戏(一)

#include <iostream>

using namespace std;

int main() 
{
    int n;
    cin>>n;
  //jingen
    int a[200010];
    int ma=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    if(a[1]==0&&n!=1)
    {
        cout<<"false";
        return 0;
    }
    if(n==1)
    {
        cout<<"true";
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=0)
        {
            ma=max(ma,a[i]+i);
            if(ma>=n)
            {
                cout<<"true";
                return 0;
            }
        }
        else 
        {
            int j=i;
            i=min(n,ma);
            while(a[j]==0)
            {
                j++;
            }
            if(j<i)
            {
                for(int k=j;k<=i;k++)
                {
                    ma=max(a[k]+k,ma);
                    if(ma>=n)
                    {
                        cout<<"true";
                        return 0;
                    }
                }
            }
            if(a[i]==0)
            {
                cout<<"false";
                return 0;
            }
            else ma=max(ma,a[i]+i);
        }
    }
    cout<<"true";
    return 0;
}

由题目观察，当n=1时，起点即为终点。其他情况用ma判断当前能到达的最远距离，当a[i]=0时，判断是否能更新到非零位置，并判断其间是否存在非零位置，返回继续更新ma，当ma>=n,则到达终点。参与链接