CSP-J 2019公交换乘题解析：基于队列优化的动态规划代码详解
https://www.xinaozhilu.cn/zb_users/upload/2025/06/202506071749228611231863.jpg一、题目解读CSP-J 2019年的“公交换乘”题目（洛谷P5661）要求模拟地铁与公交交替出行的费用计算。题目核心在于地铁消费会产生优惠券，而公交可在45分钟内使用优惠券抵扣车费。需要处理n条出行记录，优化总费用。该问题考察对时间窗口与动态资源管理的理解，需平衡实时状态更新与历史数据利用。二、解题思路代码采用“队列+动态规划”策略： 1. 使用队列存储优惠券，遵循“先进先出”原则，确保优惠券按获取时间排序。 2. 地铁消费时生成新券并入队，公交消费时检查队首券是否过期： 过期券出队，避免无效抵扣。 遍历剩余券，优先使用面值≥公交费用的券，首次匹配成功即停止（贪心策略）。 3. 未使用券暂存临时队列，最终恢复至主队列，维持原顺序。此思路将时间复杂度控制在O(n)，避免重复遍历，同时保证状态一致性。三、解题步骤1. 输入处理：读取n条记录，每条含类型（0/1）、费用、时间。2. 地铁处理（type=0）： 累加费用至总账。 生成新券（面值=费用，时间=当前时间）入队。3. 公交处理（type=1）： 清理过期券。 循环优惠券队列： 若券面值≥公交费且未使用过，标记使用并跳出循环。 否则将券暂存临时队列。 若未找到可用券，累加公交费至总账。 将临时队列券恢复至主队列。4. 输出总费用。四、代码与注释#include <iostream>
#include <queue>
using namespace std;
struct Coupon {
int price;// 地铁票价（优惠券面值）
int time; // 获得优惠券的时间
};
int main() {
ios::sync_with_stdio(false);// 加快输入输出
cin.tie(nullptr);
int n, total = 0;
cin >> n;
queue<Coupon> coupons;// 优惠券队列（先进先出）
for (int i = 0; i < n; ++i) {
int type, price, time;
cin >> type >> price >> time;
if (type == 0) {// 地铁记录
total += price;// 地铁必须付费
coupons.push({price, time});// 生成优惠券
}
else {// 公交记录
// 移除过期优惠券（队首是最早的）
while (!coupons.empty() && time - coupons.front().time > 45) {
coupons.pop();
}
bool used = false;
// 临时队列用于恢复未使用的优惠券
queue<Coupon> temp;
// 尝试使用优惠券
while (!coupons.empty()) {
Coupon c = coupons.front();
coupons.pop();
if (!used && c.price >= price) {// 找到可用优惠券
used = true;// 标记已使用
}
else {// 未使用的优惠券暂存
temp.push(c);
}
}
// 恢复未使用的优惠券
while (!temp.empty()) {
coupons.push(temp.front());
temp.pop();
}
if (!used) total += price;// 没有可用优惠券则付费
}
}
cout << total << endl;
return 0;
}
五、总结该解法巧妙运用队列实现“时间窗口”管理，结合动态规划思想降低复杂度。关键点在于： 1. 优惠券队列的FIFO特性自动维护时效。 2. 临时队列保障未使用券的状态还原。 3. 单次公交消费仅需遍历当前有效券，避免全局搜索。此思路为处理带时间限制的资源复用问题提供了经典模板，适用于类似场景的算法设计。来源：CSP题解
页:
[1]