---

想了半天做不出来,看了前辈们的答案有点自己的感悟,故献丑写下此题解。

首先要先理解题意,本题通俗理解就是要在换车之前在能到达的范围内选取换车后能到的最远距离。这么说有点绕,拿第二组数据来举例2 3 1 1 4 5,将其记为a[1~5],故能到达的范围为a[2]、a[3],而所能到达的最远范围又需加上自己所在位置,故若在a[2]换车,则能行驶a[2]+2,a[3]也是同理(其能行驶a[3]+3),此时再看加粗字体也许就能理解了,故若要以最少换车次数到达终点则需每次选取能到最远的停车场换车。

代码如下:

#include <bits/stdc++.h>

using namespace std;

int main()

{

  int t;

  cin >> t;

  for (int i = 0; i < t; i++)

  {

    int a[10001];

    int n;

    cin >> n;

    for (int j = 1; j <= n; j++) // 为了方便计算从1开始存放数据

    {

      cin >> a[j];

    }

    if (a[1] >= n - 1) // 表明不用停车就可到达终点

    {

      cout << 0 << "\n";

      continue;

    }

 

    int range = a[1] + 1; // 表示此次不换车前能到的最远距离,+1是因为已经走了一步

    int cnt = 0;        ...