题解 | 孙老师的救赎

题目链接：https://ac.nowcoder.com/acm/contest/94570/B

在这次冒险中，sml 面前有一条充满障碍的“跳跃之路”，这条路被描述为一个数组。数组中的每个元素表示 sml 在该位置最多可以跳跃的格数。例如，如果某个位置上的数字是 3，则 sml 从该位置可以选择跳跃 1、2 或 3 格，但不能跳得比 3 格更远。 sml 的目标是从数组的第一个位置出发，通过连续跳跃，尽力到达数组的最后一个位置，成功找到曹老师所在的深坑并将他救出！ 然而，跳跃之路险象环生，有的地方跳跃距离很短，稍有不慎就可能掉入陷阱，导致救援任务失败！ 你的任务是帮助 sml 判断他能否成功到达数组的最后一个位置。如果可以，请返回 true，表示 sml 成功救出曹老师；如果不行，请返回 false，表示救援任务失败，曹老师只能在坑里继续等待。

解析：

观察题目可知，第i个位置可以跳跃到的范围为res[i] = [ i , i + q[i] ]，因此我们可以先求出，对于每个点，最远可以跳到哪里

for(int i = 0;i<n;i++)
{
    res[i] = i + q[i];
}

再次遍历，求出从第一个点能跳到的最远位置max为多少？

int max = res[0];
int i = 0;	//当前位置i
while(i<=max) //当前位置大于能跳到的最远位置时，停止跳跃
{
    if(max >= n - 1) break; //当能救出曹老师时，可直接停止
    if(res[i]>max) max = res[i];
    i++;
}

最后判断 max 与 n-1 的关系即可 代码：

#include <iostream>
using namespace std;
const int N = 1e4+10;
int q[N],res[N];
int main(){
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i = 0;i<n;i++)
        {
            cin>>q[i];
            res[i] = i + q[i];
        }
        int max = res[0];
        int i = 0;
        while(i<=max)
        {
            if(max >= n - 1) break;
            if(res[i]>max) max = res[i];
            i++;
            //cout<<max<<endl;
        }
        if(max >= n - 1)
            cout<<"true"<<endl;
        else
            cout<<"false"<<endl;
    }
    
    return 0;
}