洛谷P2190题：差分数组与贪心算法的完美结合

一、问题核心分析
这个春运车厢分配问题需要考虑以下特点：

1. 环形路线：火车在n个站点间循环运行

2. 动态上下车：每个站点都有乘客上下车

3. 容量计算：需要找出整个运行过程中的最大乘客量

二、算法选择

1. 差分数组：高效处理区间增减操作

2. 前缀和：快速计算任意时刻的乘客数量

3. 贪心算法：直接取最大值计算车厢数

三、关键技术实现

1. 差分数组处理：

• 普通区间[x,y)：直接应用差分

• 环形区间[x,n]+[1,y)：拆分为两个区间处理

2. 乘客数计算：

• 通过前缀和还原实际乘客数

• 实时更新最大乘客数

3. 车厢计算：

• 向上取整公式：(max_passengers + 35)/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;
}

五、优化空间

1. 输入输出优化：使用更快的IO方法

2. 空间优化：根据n的范围调整数据结构

3. 并行处理：大数据量时的分段计算

六、常见错误

1. 环形情况处理不完整

2. 差分数组边界错误

3. 最大乘客数更新不及时

4. 车厢数计算未考虑取整

通过这个案例，我们学会了如何用简单而高效的数据结构解决看似复杂的运输调度问题，这种思路可以应用于许多类似的资源分配场景中。

参考：洛谷2190题解