2019年CSP-J 公交换乘问题详解：队列模拟与优惠券管理策略
https://dajuwangluo.cn/zb_users/upload/2025/06/202506081749361067862301.jpg一、问题背景与需求分析题目模拟城市交通卡优惠规则：[*]乘坐地铁获得等额优惠券（票价×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分钟时的处理
[*]连续多次公交使用同一优惠券
[*]调试建议：
[*]打印优惠券队列状态
[*]记录每次操作后的总金额
[*]构造极端测试用例（如全部公交或全部地铁）
[*]易错点警示：
[*]忘记处理优惠券过期
[*]错误计算时间差
[*]优惠券使用后未正确移除
来源：信奥赛学习
页:
[1]