洛谷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)，分别差分处理。

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

4. 计算车厢数：根据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)。掌握此类“差分思想”对处理动态区间问题至关重要。代码简洁且逻辑清晰，为同类问题提供了优秀模板。

来源：信奥自学之路