区间加法与最大值查询C++实现（差分数组/暴力模拟）

根据你的问题，这是一个典型的**区间加法 + 单点最大值查询**问题。由于 n ≤ 99，q 范围未明确但通常较小，我们可以直接使用**差分数组 + 前缀和**，或者**暴力模拟**即可满足要求。 下面我会给出一个**C++ 解法**，并附带详细注释。 --- ## 🧹 问题分析 - 有 n 个区域，初始干净度为 0。 - 每次操作将区间 [Li, Ri] 的干净度增加 xi。 - 经过 q 次操作后，找出所有区域中干净度的最大值。 --- ## 🧮 解法思路 ### 方法一：直接模拟（适合 n ≤ 99） - 用一个数组 `area[]` 记录每个区域的干净度。 - 每次操作遍历区间 [Li, Ri]，累加 xi。 - 最后遍历数组找最大值。 ### 方法二：差分数组（更高效） - 用差分数组 `diff[]` 记录变化。 - 每次操作：`diff[Li] += xi`，`diff[Ri+1] -= xi`。 - 最后做前缀和得到每个区域的干净度。 - 遍历找最大值。 --- ## 💻 C++ 代码实现（方法一：直接模拟） ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, q; cin >> n >> q; // 输入区域数和操作次数 vector<int> area(n + 1, 0); // 下标从1开始 for (int i = 0; i < q; i++) { int L, R, x; cin >> L >> R >> x; for (int j = L; j <= R; j++) { area[j] += x; // 区间内每个区域干净度增加x } } // 找出最大值 int maxClean = 0; for (int i = 1; i <= n; i++) { maxClean = max(maxClean, area[i]); } cout << maxClean << endl; return 0; } ``` --- ## 💻 C++ 代码实现（方法二：差分数组） ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, q; cin >> n >> q; vector<int> diff(n + 2, 0); // 差分数组，多开一个防止越界 for (int i = 0; i < q; i++) { int L, R, x; cin >> L >> R >> x; diff[L] += x; diff[R + 1] -= x; } // 前缀和得到每个区域的干净度 vector<int> area(n + 1, 0); int maxClean = 0; for (int i = 1; i <= n; i++) { area[i] = area[i - 1] + diff[i]; maxClean = max(maxClean, area[i]); } cout << maxClean << endl; return 0; } ``` --- ## ✅ 输入输出示例 **输入：** ``` 5 3 1 3 2 2 4 1 1 5 3 ``` **过程说明：** - 第1次：区域1~3 增加2 → [2,2,2,0,0] - 第2次：区域2~4 增加1 → [2,3,3,1,0] - 第3次：区域1~5 增加3 → [5,6,6,4,3] **输出：** ``` 6 ``` --- ## 🧠 开发注意点 - 数组下标从1开始更方便处理区间。 - 差分数组需要多开一位，防止 R+1 越界。 - 使用 `vector` 动态分配，适合 n 不超过 99 的情况。 - 如果 q 较大，建议使用差分数组，避免 O(n*q) 超时。 ######[AI问答 | 912点数解答 | 2026-06-20 22:38:12]