题解：P13455 [GCJ 2008 Qualification] Train Timetable

· · 题解

题目分析

我们需要计算两个车站分别需要的最少初始列车数量。解答本问题的关键点在于列车的复用，也就是说一列列车在完成行程并经过周转时间后，可以在同一车站执行下一次出发任务。

因此，我们希望通过复用列车以尽可能减少初始准备列车的数量。

$B$ 站初始准备的列车数量 = $\text{NB}$ - 可复用的列车数量（$A\rightarrow B$ 行程到达 $B$ 站并周转后的列车）。 **贪心策略**：优先使用最早可用的列车来满足最早出发的需求。 Tip：由于出发和到达在同一天且时间为 $24$ 时制，我们可以将所有的时间转换为分钟进行计算。 ### 算法分析 我们使用两个**优先级队列** `pq1`，`pq2` 维护在 $A$ 站最早可用列车时间以及在 $B$ 站最早可用列车时间。 将 $A \rightarrow B$ 行程的到达时间 + 周转时间（$t$） 存入 `pq2`。 将 $B \rightarrow A$ 行程的到达时间 + 周转时间（$t$） 存入 `pq1`。 再对 $A$ 站和 $B$ 站的列车以**出发时间**从小到大排序。 **$A$ 站**：遍历每个出发时间，若 `pq1` 中有可用列车（队头 $\le$ 出发时间），则复用该列车；否则增加一辆初始列车。 **$B$ 站**：遍历每个出发时间，若 `pq2` 中有可用列车（队头 $\le$ 出发时间），则复用该列车；否则增加一辆初始列车。 ### 细节 **1. 时间转换** 形如 $\text{hh}:\text{mm}$ 的时间信息，我们可以利用字符跳过时间格式中的冒号 ```cpp int h1, m1, h2, m2; char ch; cin >> h1 >> ch >> m1 >> h2 >> ch >> m2; ``` **2. 优先级队列（最小堆）** ```cpp priority_queue<int, vector<int>, greater<int>> pq; ``` ### 代码 ```cpp #include <bits/stdc++.h> using namespace std; int T, t, na, nb, h1, m1, h2, m2; int a[101], b[101]; char ch; void solve(int test) { priority_queue<int, vector<int>, greater<int> > pq1, pq2; // 两个最小堆维护最早完成周转的列车时间 int ca = 0, cb = 0; // 统计答案 cin >> t >> na >> nb; for (int i = 0; i < na; i++) { cin >> h1 >> ch >> m1 >> h2 >> ch >> m2; a[i] = h1 * 60 + m1; // A 站出发时间， h * 60 + m 将小时制转为分钟制 pq2.push(h2 * 60 + m2 + t); // 维护到达 B 站并周转完成的最早列车 } for (int i = 0; i < nb; i++) { cin >> h1 >> ch >> m1 >> h2 >> ch >> m2; b[i] = h1 * 60 + m1; // B 站出发时间 pq1.push(h2 * 60 + m2 + t); // 维护到达 A 站并周转完成的最早列车 } sort(a, a + na), sort(b, b + nb); // 对出发时间从小到大排序 for (int i = 0; i < na; i++) { if (pq1.size() && pq1.top() <= a[i]) { // 若有车可用(完成调度的时间 <= 出发时间) pq1.pop(); // 使用该车 } else { ca++; // 增加列车 } } for (int i = 0; i < nb; i++) { if (pq2.size() && pq2.top() <= b[i]) { pq2.pop(); } else { cb++; } } printf("Case #%d: %d %d\n", test, ca, cb); } int main() { cin >> T; for (int i = 1; i <= T; i++) solve(i); return 0; } ``` - **时间复杂度**: $\Omicron(n \log{n})