2019年CSP-J 公交换乘问题详解：队列模拟与优惠券管理策略

rhsgfswg

一、问题背景与需求分析

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

• 乘坐地铁获得等额优惠券（票价×1，有效期45分钟）
• 乘坐公交时可使用未过期优惠券抵扣
• 计算最终总支出
  
  

‌核心难点‌：

• 优惠券的时效性管理（45分钟有效期）
• 优惠券使用策略（优先使用最早获得的）
• 高效处理大量乘车记录（n ≤ 10^5）
  
  

二、完整代码实现（带详细注释）

1. #include <iostream>
   
2. #include <queue>
   
3. using namespace std;
   
4. 
   
5. // 优惠券结构体：存储面值和时间戳
   
6. struct Coupon {
   
7.     int price;  // 地铁票价（优惠券面值）
   
8.     int time;   // 获得优惠券的时间（分钟）
   
9. };
   
10. 
    
11. int main() {
    
12.     ios::sync_with_stdio(false);  // 关闭同步提升IO速度
    
13.     cin.tie(nullptr);             // 解除cin与cout的绑定
    
14.    
    
15.     int n, total = 0;            // n:记录总数 total:总支出
    
16.     cin >> n;
    
17.     queue<Coupon> coupons;       // 优惠券队列（先进先出）
    
18.    
    
19.     for (int i = 0; i < n; ++i) {
    
20.         int type, price, time;
    
21.         cin >> type >> price >> time;
    
22.         
    
23.         if (type == 0) {  // 地铁记录
    
24.             total += price;       // 地铁必须全额支付
    
25.             coupons.push({price, time});  // 生成等额优惠券
    
26.         }
    
27.         else {  // 公交记录
    
28.             // 阶段1：清理过期优惠券（队首最早）
    
29.             while (!coupons.empty() && time - coupons.front().time > 45) {
    
30.                 coupons.pop();  // 移除过期优惠券
    
31.             }
    
32.             
    
33.             bool used = false;  // 标记是否找到可用优惠券
    
34.             queue<Coupon> temp; // 临时队列暂存未使用的优惠券
    
35.             
    
36.             // 阶段2：尝试使用优惠券
    
37.             while (!coupons.empty()) {
    
38.                 Coupon c = coupons.front();
    
39.                 coupons.pop();
    
40.                
    
41.                 if (!used && c.price >= price) {  // **找到可用优惠券
    
42.                     used = true;  // 标记已使用（不实际扣除金额）
    
43.                 }
    
44.                 else {  // 未使用的优惠券暂存
    
45.                     temp.push(c);
    
46.                 }
    
47.             }
    
48.             
    
49.             // 阶段3：恢复未使用的优惠券
    
50.             while (!temp.empty()) {
    
51.                 coupons.push(temp.front());
    
52.                 temp.pop();
    
53.             }
    
54.             
    
55.             if (!used) total += price;  // 无可用优惠券则支付
    
56.         }
    
57.     }
    
58.    
    
59.     cout << total << endl;
    
60.     return 0;
    
61. }

复制代码

三、算法核心思想解析

• ‌1.队列特性应用‌：

  
  
  • 天然满足"先进先出"特性，最早获得的优惠券**被考虑
  • 队首元素永远是最早获得的优惠券
    
    

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

  
  
  • ‌清理阶段‌：移除所有过期优惠券（时间差>45分钟）
  • ‌匹配阶段‌：寻找**个满足条件的优惠券（面值≥公交票价）
  • ‌恢复阶段‌：保留未使用的有效优惠券
    
    

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

  
  
  • 最坏情况O(n^2)（当所有优惠券都无法使用时）
  • 实际运行效率较高（优惠券通常能及时使用）
    
    

四、优化思路与变种问题

• ‌性能优化‌：

  
  
  • 使用双队列减少元素搬移
  • 提前终止搜索（找到可用优惠券后立即停止）
    
    

• ‌规则变种‌：

  
  
  • 优惠券可叠加使用
  • 不同交通工具产生不同面值优惠券
  • 动态调整优惠券有效期
    
    

• ‌实际应用扩展‌：

  
  
  • 商场优惠券管理系统
  • 会员积分兑换系统
  • 多平台优惠券聚合使用
    
    

五、常见错误与调试技巧

• ‌边界条件‌：

  
  
  • 时间差刚好45分钟时的处理
  • 连续多次公交使用同一优惠券
    
    

• ‌调试建议‌：

  
  
  • 打印优惠券队列状态
  • 记录每次操作后的总金额
  • 构造极端测试用例（如全部公交或全部地铁）
    
    

• ‌易错点警示‌：

  
  
  • 忘记处理优惠券过期
  • 错误计算时间差
  • 优惠券使用后未正确移除
    
    

来源：信奥赛学习