2019年CSP-J 公交换乘问题详解：队列模拟与优惠券管理策略
一、问题背景与需求分析
题目模拟城市交通卡优惠规则：
乘坐地铁获得等额优惠券（票价×1，有效期45分钟）
乘坐公交时可使用未过期优惠券抵扣
计算最终总支出
核心难点：
优惠券的时效性管理（45分钟有效期）
优惠券使用策略（优先使用最早获得的）
高效处理大量乘车记录（n ≤ 10^5）
二、完整代码实现（带详细注释）
#include <iostream>
#include <queue>
using namespace std;
// 优惠券结构体：存储面值和时间戳
struct Coupon {
int price; // 地铁票价（优惠券面值）
int time; // 获得优惠券的时间（分钟）
};
int main() {
ios::sync_with_stdio(false); // 关闭同步提升IO速度
cin.tie(nullptr); // 解除cin与cout的绑定
int n, total = 0; // n:记录总数 total:总支出
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 { // 公交记录
// 阶段1：清理过期优惠券（队首最早）
while (!coupons.empty() && time - coupons.front().time > 45) {
coupons.pop(); // 移除过期优惠券
}
bool used = false; // 标记是否找到可用优惠券
queue<Coupon> temp; // 临时队列暂存未使用的优惠券
// 阶段2：尝试使用优惠券
while (!coupons.empty()) {
Coupon c = coupons.front();
coupons.pop();
if (!used && c.price >= price) { // 首次找到可用优惠券
used = true; // 标记已使用（不实际扣除金额）
}
else { // 未使用的优惠券暂存
temp.push(c);
}
}
// 阶段3：恢复未使用的优惠券
while (!temp.empty()) {
coupons.push(temp.front());
temp.pop();
}
if (!used) total += price; // 无可用优惠券则支付
}
}
cout << total << endl;
return 0;
}三、算法核心思想解析
1.队列特性应用：
天然满足"先进先出"特性，最早获得的优惠券最先被考虑
队首元素永远是最早获得的优惠券
2.三阶段处理流程：
清理阶段：移除所有过期优惠券（时间差>45分钟）
匹配阶段：寻找第一个满足条件的优惠券（面值≥公交票价）
恢复阶段：保留未使用的有效优惠券
3.时间复杂度分析：
最坏情况O(n^2)（当所有优惠券都无法使用时）
实际运行效率较高（优惠券通常能及时使用）
四、优化思路与变种问题
性能优化：
使用双队列减少元素搬移
提前终止搜索（找到可用优惠券后立即停止）
规则变种：
优惠券可叠加使用
不同交通工具产生不同面值优惠券
动态调整优惠券有效期
实际应用扩展：
商场优惠券管理系统
会员积分兑换系统
多平台优惠券聚合使用
五、常见错误与调试技巧
边界条件：
时间差刚好45分钟时的处理
连续多次公交使用同一优惠券
调试建议：
打印优惠券队列状态
记录每次操作后的总金额
构造极端测试用例（如全部公交或全部地铁）
易错点警示：
忘记处理优惠券过期
错误计算时间差
优惠券使用后未正确移除
链接：动态规划
原创内容 转载请注明出处
