专栏文章

题解：P13455 [GCJ 2008 Qualification] Train Timetable

AAHOI_Capzera
P13455题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miok15y7
此快照首次捕获于
2025/12/02 20:28
3 个月前
此快照最后确认于
2025/12/02 20:28
3 个月前
查看原文

题目分析

我们需要计算两个车站分别需要的最少初始列车数量。解答本问题的关键点在于列车的复用，也就是说一列列车在完成行程并经过周转时间后，可以在同一车站执行下一次出发任务。
因此，我们希望通过复用列车以尽可能减少初始准备列车的数量。
AA 站初始准备的列车数量 = NA\text{NA} - 可复用的列车数量（B→AB\rightarrow A 行程到达 AA 站并周转后的列车）。
BB 站初始准备的列车数量 = NB\text{NB} - 可复用的列车数量（A→BA\rightarrow B 行程到达 BB 站并周转后的列车）。
贪心策略：优先使用最早可用的列车来满足最早出发的需求。
Tip：由于出发和到达在同一天且时间为 2424 时制，我们可以将所有的时间转换为分钟进行计算。

算法分析

我们使用两个优先级队列 pq1，pq2 维护在 AA 站最早可用列车时间以及在 BB 站最早可用列车时间。
将 A→BA \rightarrow B 行程的到达时间 + 周转时间（tt） 存入 pq2。
将 B→AB \rightarrow A 行程的到达时间 + 周转时间（tt） 存入 pq1。
再对 AA 站和 BB 站的列车以出发时间从小到大排序。
AA 站：遍历每个出发时间，若 pq1 中有可用列车（队头 ≤\le 出发时间），则复用该列车；否则增加一辆初始列车。
BB 站：遍历每个出发时间，若 pq2 中有可用列车（队头 ≤\le 出发时间），则复用该列车；否则增加一辆初始列车。

细节

1. 时间转换
形如 hh:mm\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;
}
  • 时间复杂度: O(nlog⁡n)\Omicron(n \log{n})
    • 排序出发时间数组: O(nlog⁡n+mlog⁡m)\Omicron(n \log{n} + m \log{m})
    • 优先级队列操作: 每个元素入队出队一次 O(log⁡n)\Omicron(\log{n}) 或 O(log⁡m)\Omicron(\log{m})
  • 空间复杂度: O(n+m)\Omicron(n + m)
    • 存储出发时间数组: O(n+m)\Omicron(n + m)
    • 优先级队列: O(n+m)\Omicron(n + m)

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...