一、题目解读
洛谷P2190题要求解决铁路售票系统中的车厢数量计算问题。题目给定n个车站和m条订票申请,每条申请包含区间[x,y)及乘客数z。需要计算在不超载的情况下(每节车厢最多36人),满足所有乘客需求所需的最小车厢数。问题关键在于高效处理区间修改与统计最大值。
二、解题思路
核心思路是利用差分数组+前缀和实现区间修改的优化。通过差分数组记录每个站点的乘客变化(如进入/离开人数),再计算前缀和得到各站点的实时乘客数,从而找出最大值。特别处理环形区间(即x>y时,拆分为两段处理),确保逻辑完整性。
三、解题步骤
输入与初始化:读入n、m,创建长度为n+2的差分数组(多留两端便于边界处理)。
处理订票申请:
○ 普通区间(x≤y):在x位置+乘客数z,y位置-乘客数z(差分核心)。
○ 环形区间(x>y):拆分为两段:[x,n]和[1,y),分别差分处理。
计算前缀和:遍历差分数组,累加当前值并更新最大乘客数。
计算车厢数:根据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)。掌握此类“差分思想”对处理动态区间问题至关重要。代码简洁且逻辑清晰,为同类问题提供了优秀模板。