ad1 广告
 
收藏文章 楼主

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

版块:网络百科   类型:普通   作者:某个人   查看:17   回复:0   获赞:0   时间:2025-06-16 15:43:46

CSP-J 2019公交换乘题解析:基于队列优化的动态规划代码详解 2019 公交换乘题 队列优化 动态规划 时间复杂度 第1张

一、题目解读

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

二、解题思路

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

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

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

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

        遍历剩余券,优先使用面值≥公交费用的券,首次匹配成功即停止(贪心策略)。

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

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

三、解题步骤

1. 输入处理:读取n条记录,每条含类型(0/1)、费用、时间。

2. 地铁处理(type=0):

    累加费用至总账。

    生成新券(面值=费用,时间=当前时间)入队。

3. 公交处理(type=1):

    清理过期券。

    循环优惠券队列:

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

        否则将券暂存临时队列。

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

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

4. 输出总费用。

四、代码与注释

#include <iostream>  
#include <queue>  
using namespace std;  

struct Coupon {  
    int price;  // 地铁票价(优惠券面值)  
    int time;   // 获得优惠券的时间  
};  

int main() {  
    ios::sync_with_stdio(false);  // 加快输入输出  
    cin.tie(nullptr);           
  
    int n, total = 0;  
    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 {  // 公交记录  
            // 移除过期优惠券(队首是最早的)  
            while (!coupons.empty() && time - coupons.front().time > 45) {  
                coupons.pop();  
            }  

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

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

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

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

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

    cout << total << endl;  
    return 0;  
}

五、总结

该解法巧妙运用队列实现“时间窗口”管理,结合动态规划思想降低复杂度。关键点在于:

    1. 优惠券队列的FIFO特性自动维护时效。

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

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

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

原文:动态规划

 
ad1 广告位8,870 x auto
回复列表
默认   热门   正序   倒序

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

Powered by 免费外链论坛

©2015 - 2025 免费外链论坛

免费外链论坛 免费发布外链 发外链平台Sitemap

您的IP:216.73.216.212,2025-07-01 21:55:44,Processed in 0.02834 second(s).

备案信息:浙ICP备2024090696号

声明:本站内容为用户自主发布,不对其内容真实性负责,虽然本站会一一审核,但能力有限,如您发现违规内容,请及时联系管理员。

主页

欢迎您的浏览

QQ联系图标

自助查询

99%的问题都能找到答案

联系站长

工作时间:9:00~17:30

微信二维码

回到顶部

向上滚动到顶部

个人中心

去个人首页看看吧

转到底部

向下滚动到底部

头像

用户名:

粉丝数:

签名:

资料 关注 好友 消息