小苯的格子移动

[题目链接](https://www.nowcoder.com/practice/d1c43a534cb943398e6fafcc5e27aefb)

思路

数轴上有 $n$ 个格子，第 $i$ 个格子的解锁时间为 $a_i$ （保证 $a_1 = 0$ ）。从第 1 个格子出发，每秒可以移动到下一个格子（前提是已解锁）或原地等待。求到达第 $n$ 个格子的最少时间。

贪心模拟

用 $cur$ 记录当前时间，初始为 0（在第 1 格）。依次考虑移动到第 $2, 3, \ldots, n$ 格：

移动需要 1 秒，所以最早到达时间为 $cur + 1$ ；
同时第 $i$ 格需要在 $a_i$ 时刻后才能到达。

因此到达第 $i$ 格的最早时间为：

$ $cur = \max(cur + 1, a_i)$ $

这是最优策略：能走就走，不能走就等。不存在"提前等待"能获得更优解的情况，因为每一步都是往右走一格，越早到达当前格子，后续的灵活性越大。

样例演示

第一组 $a = [0, 2, 4, 2, 4]$ ：

步骤	目标格子	$\max(cur+1, a_i)$	$cur$
初始	1	-	0
1	2	$\max(1, 2) = 2$	2
2	3	$\max(3, 4) = 4$	4
3	4	$\max(5, 2) = 5$	5
4	5	$\max(6, 4) = 6$	6

答案为 6。

复杂度分析

时间复杂度： $O(n)$ ，单次遍历。
空间复杂度： $O(n)$ ，存储数组（也可边读边算做到 $O(1)$ ）。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        vector<long long> a(n);
        for(int i=0;i<n;i++) scanf("%lld",&a[i]);
        long long cur=0;
        for(int i=1;i<n;i++){
            cur = max(cur+1, a[i]);
        }
        printf("%lld\n",cur);
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while(t-- > 0){
            int n = Integer.parseInt(br.readLine().trim());
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            long[] a = new long[n];
            for(int i=0;i<n;i++) a[i] = Long.parseLong(st.nextToken());
            long cur = 0;
            for(int i=1;i<n;i++){
                cur = Math.max(cur+1, a[i]);
            }
            sb.append(cur).append('\n');
        }
        System.out.print(sb);
    }
}