洛谷P2190题解：铁路售票系统车厢计算（差分数组+前缀和...

19339201706

一、题目解读

洛谷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人/车厢的规则，向上取整得到最终结果。

四、代码与注释

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. int main() {
   
7.     int n, m;  
   
8.     cin >> n >> m;  
   
9. 
   
10.     // 差分数组，记录每个站点的乘客变化  
    
11.     vector<int> diff(n + 2, 0);  
    
12. 
    
13.     // 处理每条订票申请  
    
14.     for (int i = 0; i < m; ++i) {  
    
15.         int x, y, z;  
    
16.         cin >> x >> y >> z;  
    
17. 
    
18.         if (x <= y) {  
    
19.             // 普通区间[x,y)  
    
20.             diff[x] += z;  
    
21.             diff[y] -= z;  
    
22.         } else {  
    
23.             // 环形区间[x,n]和[1,y)  
    
24.             diff[x] += z;  
    
25.             diff[n+1] -= z;  
    
26.             diff[1] += z;  
    
27.             diff[y] -= z;  
    
28.         }  
    
29.     }  
    
30. 
    
31.     // 计算前缀和，找出最大乘客数  
    
32.     int max_passengers = 0;  
    
33.     int current = 0;  
    
34.     for (int i = 1; i <= n; ++i) {  
    
35.         current += diff[i];  
    
36.         max_passengers = max(max_passengers, current);  
    
37.     }  
    
38. 
    
39.     // 计算所需车厢数（每节36人）  
    
40.     int carriages = (max_passengers + 35) / 36;  
    
41.     cout << carriages << endl;  
    
42. 
    
43.     return 0;  
    
44. }

复制代码

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

五、总结

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

来源：信奥自学之路