CSP-J 2019公交换乘题解析：基于队列优化的动态规划代码详解

胡志明t

一、题目解读

CSP-J 2019年的“公交换乘”题目（洛谷P5661）要求模拟地铁与公交交替出行的费用计算。题目核心在于地铁消费会产生优惠券，而公交可在45分钟内使用优惠券抵扣车费。需要处理n条出行记录，优化总费用。该问题考察对时间窗口与动态资源管理的理解，需平衡实时状态更新与历史数据利用。

二、解题思路

代码采用“队列+动态规划”策略：

    1. 使用队列存储优惠券，遵循“先进先出”原则，确保优惠券按获取时间排序。

    2. 地铁消费时生成新券并入队，公交消费时检查队首券是否过期：

        过期券出队，避免无效抵扣。

        遍历剩余券，优先使用面值≥公交费用的券，**匹配成功即停止（贪心策略）。

    3. 未使用券暂存临时队列，最终恢复至主队列，维持原顺序。

此思路将时间复杂度控制在O(n)，避免重复遍历，同时保证状态一致性。

三、解题步骤

1. 输入处理：读取n条记录，每条含类型（0/1）、费用、时间。

2. 地铁处理（type=0）：

    累加费用至总账。

    生成新券（面值=费用，时间=当前时间）入队。

3. 公交处理（type=1）：

    清理过期券。

    循环优惠券队列：

        若券面值≥公交费且未使用过，标记使用并跳出循环。

        否则将券暂存临时队列。

        若未找到可用券，累加公交费至总账。

    将临时队列券恢复至主队列。

4. 输出总费用。

四、代码与注释

1. #include <iostream>  
   
2. #include <queue>  
   
3. using namespace std;  
   
4. 
   
5. struct Coupon {  
   
6.     int price;  // 地铁票价（优惠券面值）  
   
7.     int time;   // 获得优惠券的时间  
   
8. };  
   
9. 
   
10. int main() {  
    
11.     ios::sync_with_stdio(false);  // 加快输入输出  
    
12.     cin.tie(nullptr);           
    
13.   
    
14.     int n, total = 0;  
    
15.     cin >> n;  
    
16.     queue<Coupon> coupons;  // 优惠券队列（先进先出）  
    
17. 
    
18.     for (int i = 0; i < n; ++i) {  
    
19.         int type, price, time;  
    
20.         cin >> type >> price >> time;  
    
21. 
    
22.         if (type == 0) {  // 地铁记录  
    
23.             total += price;  // 地铁必须付费  
    
24.             coupons.push({price, time});  // 生成优惠券  
    
25.         }  
    
26.         else {  // 公交记录  
    
27.             // 移除过期优惠券（队首是最早的）  
    
28.             while (!coupons.empty() && time - coupons.front().time > 45) {  
    
29.                 coupons.pop();  
    
30.             }  
    
31. 
    
32.             bool used = false;  
    
33.             // 临时队列用于恢复未使用的优惠券  
    
34.             queue<Coupon> temp;  
    
35. 
    
36.             // 尝试使用优惠券  
    
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.             // 恢复未使用的优惠券  
    
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. 优惠券队列的FIFO特性自动维护时效。

    2. 临时队列保障未使用券的状态还原。

    3. 单次公交消费仅需遍历当前有效券，避免全局搜索。

此思路为处理带时间限制的资源复用问题提供了经典模板，适用于类似场景的算法设计。

来源：CSP-J 2019公交换乘题解析：基于队列优化的动态规划代码详解