题解 | #小苯的格子移动#

题目链接

小苯的格子移动

题目描述

在一个数轴上，有 $n$ 个从 $1$ 到 $n$ 标号的格子。每个格子 $i$ 都有一个解锁时间 $t_i$ ，意味着只有在时间大于等于 $t_i$ 秒时，才能进入该格子。

小苯初始在格子 $1$ (保证 $t_1=0$ )。每一秒，他可以选择：

从当前格子 $i$ 移动到格子 $i+1$ ，前提是格子 $i+1$ 已经解锁。
在当前格子 $i$ 等待。

求解小苯从格子 $1$ 移动到格子 $n$ 所需的最短时间。

思路分析

这是一个可以通过贪心或简单动态规划解决的问题。我们的目标是计算到达每个格子的最早可能时间。

我们定义 $time_i$ 为到达格子 $i$ 的最早时间。

初始状态: 根据题目，我们从时间 $0$ 开始就在格子 $1$ ，并且 $t_1=0$ ，所以 $time_1 = t_1 = 0$ 。
状态转移: 假设我们已经知道了到达格子 $i$ 的最早时间 $time_i$ ，现在需要计算到达下一个格子 $i+1$ 的最早时间 $time_{i+1}$ 。
1. 从格子 $i$ 移动到格子 $i+1$ 需要 $1$ 秒的时间。所以，如果我们从 $time_i$ 时刻出发，到达 $i+1$ 这个位置时，时间将变为 $time_i + 1$ 。
2. 但是，要能够停留在格子 $i+1$ ，当前时间必须不早于它的解锁时间 $t_{i+1}$ 。
3. 因此，要同时满足这两个条件，我们真正到达（即可以停留在）格子 $i+1$ 的时间，必须是这两个时间的较大值。
这就给出了我们的递推关系： $time_{i+1} = \max(time_i + 1, t_{i+1})$

我们可以从 $i=1$ 开始，一步步递推到 $i=n$ ，最终得到的 $time_n$ 就是答案。在实现上，我们不需要一个数组来存储所有 $time_i$ ，只需要一个变量来记录当前格子的到达时间，然后用它来计算下一个格子的时间即可。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int n;
    cin >> n;
    
    long long current_time;
    cin >> current_time; // 读取 t_1，作为初始时间

    for (int i = 1; i < n; ++i) {
        long long unlock_time;
        cin >> unlock_time;
        // 先花1秒移动，然后看是否需要等待解锁
        current_time = max(current_time + 1, unlock_time);
    }
    
    cout << current_time << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        
        long currentTime = sc.nextLong(); // 读取 t_1，作为初始时间

        for (int i = 1; i < n; i++) {
            long unlockTime = sc.nextLong();
            // 先花1秒移动，然后看是否需要等待解锁
            currentTime = Math.max(currentTime + 1, unlockTime);
        }
        
        System.out.println(currentTime);
    }
}

import sys

def solve():
    n = int(sys.stdin.readline())
    t = list(map(int, sys.stdin.readline().split()))
    
    current_time = t[0] # 初始时间
    
    for i in range(1, n):
        # 先花1秒移动，然后看是否需要等待解锁
        current_time = max(current_time + 1, t[i])
        
    print(current_time)

def main():
    # 本题 sys.stdin.readline 比 input 快
    # 但根据要求，若无特殊说明，倾向于使用 input
    # 不过对于多组输入且数据量大的情况，sys 是必要的
    t = int(sys.stdin.readline())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

算法：贪心 / 动态规划
时间复杂度：对于每组测试数据，我们只需要遍历一次所有格子，因此时间复杂度为 $O(n)$ 。
空间复杂度：如果我们边读取输入边计算，只需要常数个变量，空间复杂度为 $O(1)$ 。如果先将所有解锁时间读入数组，则为 $O(n)$ 。