一、问题背景与需求分析

题目模拟城市交通卡优惠规则：

1. 乘坐地铁获得等额优惠券（票价×1，有效期45分钟）

2. 乘坐公交时可使用未过期优惠券抵扣

3. 计算最终总支出

‌核心难点‌：

• 优惠券的时效性管理（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. ‌1.队列特性应用‌：

• 天然满足"先进先出"特性，最早获得的优惠券最先被考虑

• 队首元素永远是最早获得的优惠券

‌2.三阶段处理流程‌：

• ‌清理阶段‌：移除所有过期优惠券（时间差>45分钟）

• ‌匹配阶段‌：寻找第一个满足条件的优惠券（面值≥公交票价）

• ‌恢复阶段‌：保留未使用的有效优惠券

‌3.时间复杂度分析‌：

• 最坏情况O(n^2)（当所有优惠券都无法使用时）

• 实际运行效率较高（优惠券通常能及时使用）

四、优化思路与变种问题

1. ‌性能优化‌：

• 使用双队列减少元素搬移

• 提前终止搜索（找到可用优惠券后立即停止）

‌规则变种‌：

• 优惠券可叠加使用

• 不同交通工具产生不同面值优惠券

• 动态调整优惠券有效期

‌实际应用扩展‌：

• 商场优惠券管理系统

• 会员积分兑换系统

• 多平台优惠券聚合使用

五、常见错误与调试技巧

1. ‌边界条件‌：

• 时间差刚好45分钟时的处理

• 连续多次公交使用同一优惠券

‌调试建议‌：

• 打印优惠券队列状态

• 记录每次操作后的总金额

• 构造极端测试用例（如全部公交或全部地铁）

‌易错点警示‌：

• 忘记处理优惠券过期

• 错误计算时间差

• 优惠券使用后未正确移除

来源：信奥赛学习