题意分析

本题描述了一个渡船运送汽车过河的场景。在桥梁不普遍时，渡船被用于运送汽车过河，此渡船沿着引导线由水流驱动。渡船每次能载 $n$ 辆汽车，单程需 $t$ 分钟，往返共 $2t$ 分钟。汽车可到达河的左岸或右岸等待渡河，渡船只要载有汽车或者两岸有车等待就会持续往返。当渡船到达一岸，会卸载货物并装载最多 $n$ 辆等待时间最长的汽车。若两岸都无车等待，渡船会等待有车到达，若车到达的是渡船所在岸就装载过河。题目要求根据输入的测试用例，计算每辆汽车到达对岸的时间。

解题思路

1. 数据存储：使用结构体 $Node$ 存储每辆车的编号 $id$、到达时间 $time$ 以及到达对岸的时间 $ans$。用两个队列 $q[0]$ 和 $q[1]$ 分别存储左岸和右岸等待的车辆，用向量 $v$ 存储所有已确定到达对岸时间的车辆。
2. 输入处理：读取测试用例的数量 $t$，对于每个测试用例，读取 $n$（渡船每次可载车辆数）、$time$（单程时间）和 $m$（车辆总数），并将每辆车的到达时间和所在岸信息存储到对应的队列中。
3. 模拟渡船运行：使用 $start$ 标记渡船当前所在岸（0 表示左岸，1 表示右岸），$time2$ 记录当前时间。在两岸队列都不为空时，进行如下操作：
   • 尝试在当前岸装载车辆：若当前岸队列不为空，且队首车辆到达时间不晚于当前时间，且装载车辆数小于 $n$，则将该车装载，更新其到达对岸时间并加入向量 $v$，同时从队列中移除该车。
   • 根据装载情况更新时间和渡船位置：
     • 若成功装载车辆，将当前时间加上单程时间 $time$，并切换渡船到对岸。
     • 若未成功装载车辆，根据两岸队列情况更新当前时间和渡船位置：
       • 若对岸队列空，或当前岸队列首车到达时间更早，将当前时间更新为当前岸队列首车的到达时间。
       • 若对岸队列首车到达时间不晚于当前时间，将当前时间加上单程时间 $time$，并切换渡船到对岸。
       • 若对岸队列首车到达时间晚于当前时间，将当前时间更新为对岸队列首车到达时间加上单程时间 $time$，并切换渡船到对岸。
4. 结果输出：对向量 $v$ 按车辆编号排序，按顺序输出每辆车到达对岸的时间。每个测试用例结果间输出一个空行。

代码解释

/* POJ2652 HDU1146 ZOJ2550 UVA10901 Ferry Loading III */

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

// 定义结构体存储车辆信息
struct Node {
    int id, time, ans;
    friend bool operator <(Node a, Node b) { return a.id < b.id; }
    Node(int id = 0, int time = 0, int ans = -1) : id(id), time(time), ans(ans) {}
};

int main()
{
    int t, n, time, m, tm;
    char s[8];
    // 读取测试用例数量
    scanf("%d", &t);
    while(t--) {
        // 两个队列分别存储左岸和右岸等待的车辆
        queue<Node> q[2];
        // 向量存储所有已确定到达对岸时间的车辆
        vector<Node> v;

        // 读取当前测试用例的 n、time 和 m
        scanf("%d%d%d", &n, &time, &m);
        for(int i = 1; i <= m; i++) {
            // 读取每辆车的到达时间和所在岸信息
            scanf("%d%s", &tm, s);
            // 根据所在岸将车辆加入对应队列
            q[s[0] == 'l' ? 0 : 1].push(Node(i, tm, -1));
        }

        // 初始渡船在左岸，当前时间为 0
        int start = 0, time2 = 0;
        // 当两岸队列都不为空时循环
        while(!q[0].empty() || !q[1].empty()) {
            int cnt = 0;
            // 尝试在当前岸装载车辆
            while(!q[start].empty() && q[start].front().time <= time2 && cnt < n) {
                cnt++;
                // 更新车辆到达对岸的时间
                q[start].front().ans = time2 + time;
                // 将车辆加入向量 v
                v.push_back(q[start].front());
                // 从队列中移除该车
                q[start].pop();
            }

            if(cnt) {
                // 若成功装载车辆，更新时间并切换渡船到对岸
                time2 += time;
                start = 1 - start;
            } else {
                // 若未成功装载车辆，根据两岸队列情况更新时间和渡船位置
                if(q[1 - start].empty() || (!q[start].empty() && q[1 - start].front().time > q[start].front().time))
                    time2 = q[start].front().time;
                else if(!q[1 - start].empty() && q[1 - start].front().time <= time2) {
                    time2 += time;
                    start = 1 - start;
                } else if(!q[1 - start].empty() && q[1 - start].front().time > time2) {
                    time2 = q[1 - start].front().time + time;
                    start = 1 - start;
                }
            }
        }

        // 对向量 v 按车辆编号排序
        sort(v.begin(), v.end());
        // 按顺序输出每辆车到达对岸的时间
        for(int i = 0; i < (int)v.size(); i++)
            printf("%d\n", v[i].ans);
        // 每个测试用例结果间输出一个空行
        if(t) printf("\n");
    }

    return 0;
}

复杂度分析

• 时间复杂度：对于每个测试用例，需要遍历所有车辆，每次操作时间复杂度为常数级，排序操作时间复杂度为 $O(m \log m)$，其中 m 为车辆总数。假设有 t 个测试用例，则总的时间复杂度为 $O(t \times m \log m)$。
• 空间复杂度：主要使用了队列和向量存储车辆信息，空间复杂度为 $O(m)$，其中 m 为车辆总数。

注意事项

1. 队列操作：在操作队列时，要注意队列是否为空，避免出现空队列操作的错误。
2. 时间更新：在更新当前时间和渡船位置时，要仔细考虑各种情况，确保逻辑正确。
3. 输出格式：注意每个测试用例结果间要输出一个空行，严格按照题目要求的格式输出。