洛谷P2190题解:铁路售票系统车厢计算(差分数组+前缀和优化)

深度学习
• 阅读 15

洛谷P2190题解:铁路售票系统车厢计算(差分数组+前缀和优化)

一、题目解读

洛谷P2190题要求解决铁路售票系统中的车厢数量计算问题。题目给定n个车站和m条订票申请,每条申请包含区间[x,y)及乘客数z。需要计算在不超载的情况下(每节车厢最多36人),满足所有乘客需求所需的最小车厢数。问题关键在于高效处理区间修改与统计最大值。

二、解题思路

核心思路是利用差分数组+前缀和实现区间修改的优化。通过差分数组记录每个站点的乘客变化(如进入/离开人数),再计算前缀和得到各站点的实时乘客数,从而找出最大值。特别处理环形区间(即x>y时,拆分为两段处理),确保逻辑完整性。

三、解题步骤

  1. 输入与初始化:读入n、m,创建长度为n+2的差分数组(多留两端便于边界处理)。

  2. 处理订票申请:

○ 普通区间(x≤y):在x位置+乘客数z,y位置-乘客数z(差分核心)。

○ 环形区间(x>y):拆分为两段:[x,n]和[1,y),分别差分处理。

  1. 计算前缀和:遍历差分数组,累加当前值并更新最大乘客数。

  2. 计算车厢数:根据36人/车厢的规则,向上取整得到最终结果。

四、代码与注释

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m;  
    cin >> n >> m;  

    // 差分数组,记录每个站点的乘客变化  
    vector<int> diff(n + 2, 0);  

    // 处理每条订票申请  
    for (int i = 0; i < m; ++i) {  
        int x, y, z;  
        cin >> x >> y >> z;  

        if (x <= y) {  
            // 普通区间[x,y)  
            diff[x] += z;  
            diff[y] -= z;  
        } else {  
            // 环形区间[x,n]和[1,y)  
            diff[x] += z;  
            diff[n+1] -= z;  
            diff[1] += z;  
            diff[y] -= z;  
        }  
    }  

    // 计算前缀和,找出最大乘客数  
    int max_passengers = 0;  
    int current = 0;  
    for (int i = 1; i <= n; ++i) {  
        current += diff[i];  
        max_passengers = max(max_passengers, current);  
    }  

    // 计算所需车厢数(每节36人)  
    int carriages = (max_passengers + 35) / 36;  
    cout << carriages << endl;  

    return 0;  
}

注释说明:差分数组通过“延迟更新”简化区间修改操作,前缀和计算则快速还原真实乘客数。环形区间的特殊处理避免了逻辑漏洞。

五、总结

本解法通过差分数组巧妙转化区间修改为单点操作,结合前缀和高效求解最大值,时间复杂度O(n+m)。掌握此类“差分思想”对处理动态区间问题至关重要。代码简洁且逻辑清晰,为同类问题提供了优秀模板。

来源:洛谷P2190题解:铁路售票系统车厢计算(差分数组+前缀和优化)

点赞
收藏
评论区
推荐文章
贾蔷 贾蔷
1星期前
2023年GESP六级小杨握手问题(洛谷B3874):Fenwick树求解逆序对的代码解析
一、题目解读“小杨的握手问题”源自2023年GESP六级考试(对应洛谷题目B3874)。题目描述为:给定一个长度为N的排列,每次将当前数与之前未访问过的数握手,求总共握手次数。本质上是求排列中逆序对的个数,即统计每个数右侧比它小的元素数量。需设计高效算法在
贾蔷 贾蔷
1星期前
CSP-J 2019公交换乘题解析:基于队列优化的动态规划代码详解
一、题目解读CSPJ2019年的“公交换乘”题目(洛谷P5661)要求模拟地铁与公交交替出行的费用计算。题目核心在于地铁消费会产生优惠券,而公交可在45分钟内使用优惠券抵扣车费。需要处理n条出行记录,优化总费用。该问题考察对时间窗口与动态资源管理的理解,需
深度学习 深度学习
1星期前
【CSP-S 2019】括号树(洛谷P5658):栈+DFS
一、题目解读括号树问题(洛谷P5658)要求处理一个由括号序列转化的树结构:每个节点表示一个括号,'('为子节点,')'为父节点。题目给定一棵n个节点的树,需计算每个节点的深度(括号层数),并输出所有节点深度与节点编号乘积的异或和。核心在于将括号序列转化为
贾蔷 贾蔷
1星期前
牛客13279题解:利用递归与深度优先搜索计算树的最大高度(附完整代码)
一、题目解读牛客13279题要求计算给定树的最大高度。题目输入一棵以邻接表形式表示的树(节点从0开始编号),需要输出从根节点到最深叶节点的最长路径长度。树的结构由n个节点和n1条边构成,保证为连通无环图。理解题目核心在于准确获取树的拓扑关系,并设计算法遍历
深度学习 深度学习
1星期前
2024蓝桥杯省赛B组前缀总分(洛谷P12124)解题思路与代码详解
一、题目解读2024年蓝桥杯省B组题目“前缀总分”(对应洛谷P12124)要求计算给定字符串集合中,所有前缀的最长公共前缀(LCP)的总分,并找出通过移动字符位置后可能获得的最大总分。题目考察字符串处理与动态规划能力,需高效计算LCP并优化得分策略。二、解
深度学习 深度学习
1星期前
洛谷P2034题解:动态规划+单调队列优化求解最大K段子段和问题
一、题目解读洛谷P2034题目要求给定一个长度为n的整数数组,将其分成不超过k段,求各段和的最大值。该问题属于经典动态规划问题的扩展,需结合优化技巧高效求解。二、解题思路采用动态规划单调队列优化的策略。核心思想是定义状态dp
贾蔷 贾蔷
1星期前
【2023 CSP-S密码锁(洛谷P9752)】题解:动态规划与集合交集的巧妙应用
一、题目解读2023年CSPS的“密码锁”题目(洛谷P9752)要求破解一种环形密码锁机制。题目给定n组状态,每个状态由5个数字组成,通过“单拨圈”或“双相邻拨圈”操作可改变数字。正确密码需满足:通过操作能从初始状态转换到所有给定状态,且给定状态本身不能作
深度学习 深度学习
1星期前
2012年NOIP提高组「借教室」(洛谷P1083)解题思路与二分查找优化代码解析
一、题目解读本题为2012年NOIP提高组中的「借教室」问题(洛谷P1083),要求处理教室借用订单的分配问题。给定n天每天可用教室数量r和m个订单(订单包含需求教室数d、开始日期s、结束日期t),判断能否通过删除部分订单使所有订单满足教室容量限制。若能,