查看: 37|回复: 0

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

[复制链接]
  • TA的每日心情
    无聊
    13 小时前
  • 签到天数: 52 天

    [LV.5]常住居民I

    51

    主题

    0

    回帖

    86

    积分

    注册会员

    Rank: 2

    积分
    86
    发表于 7 天前 | 显示全部楼层 |阅读模式
    一、题目解读
    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. struct Coupon {  
    5.     int price;  // 地铁票价(优惠券面值)  
    6.     int time;   // 获得优惠券的时间  
    7. };  

    8. int main() {  
    9.     ios::sync_with_stdio(false);  // 加快输入输出  
    10.     cin.tie(nullptr);           
    11.   
    12.     int n, total = 0;  
    13.     cin >> n;  
    14.     queue<Coupon> coupons;  // 优惠券队列(先进先出)  

    15.     for (int i = 0; i < n; ++i) {  
    16.         int type, price, time;  
    17.         cin >> type >> price >> time;  

    18.         if (type == 0) {  // 地铁记录  
    19.             total += price;  // 地铁必须付费  
    20.             coupons.push({price, time});  // 生成优惠券  
    21.         }  
    22.         else {  // 公交记录  
    23.             // 移除过期优惠券(队首是最早的)  
    24.             while (!coupons.empty() && time - coupons.front().time > 45) {  
    25.                 coupons.pop();  
    26.             }  

    27.             bool used = false;  
    28.             // 临时队列用于恢复未使用的优惠券  
    29.             queue<Coupon> temp;  

    30.             // 尝试使用优惠券  
    31.             while (!coupons.empty()) {  
    32.                 Coupon c = coupons.front();  
    33.                 coupons.pop();  

    34.                 if (!used && c.price >= price) {  // 找到可用优惠券  
    35.                     used = true;  // 标记已使用  
    36.                 }  
    37.                 else {  // 未使用的优惠券暂存  
    38.                     temp.push(c);  
    39.                 }  
    40.             }  

    41.             // 恢复未使用的优惠券  
    42.             while (!temp.empty()) {  
    43.                 coupons.push(temp.front());  
    44.                 temp.pop();  
    45.             }  

    46.             if (!used) total += price;  // 没有可用优惠券则付费  
    47.         }  
    48.     }  

    49.     cout << total << endl;  
    50.     return 0;  
    51. }
    复制代码


    五、总结
    该解法巧妙运用队列实现“时间窗口”管理,结合动态规划思想降低复杂度。关键点在于:
        1. 优惠券队列的FIFO特性自动维护时效。
        2. 临时队列保障未使用券的状态还原。
        3. 单次公交消费仅需遍历当前有效券,避免全局搜索。
    此思路为处理带时间限制的资源复用问题提供了经典模板,适用于类似场景的算法设计。
    来源:CSP题解
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    快速回复 返回顶部 返回列表