区间批量加法与最大值求解 C++ 实现

好的，我将根据您的要求，提供一份完整、清晰、带详细注释的 C++ 代码，用于解决这个问题。 --- ## 🧹 问题分析 我们需要维护一个长度为 `n` 的数组，初始所有元素为 0。 每次操作对区间 `[Li, Ri]` 内的所有元素增加 `Xi`。 经过 `q` 次操作后，找出数组中的最大值。 由于 `n <= 99` 和 `q` 未明确限制，但题目范围较小，最简单的做法是直接模拟。 --- ## 💻 C++ 代码实现 ```cpp #include <iostream> #include <vector> #include <algorithm> // 用于 max 函数 using namespace std; int main() { // 输入 n 和 q int n, q; cin >> n >> q; // 创建一个长度为 n 的数组，初始值为 0 vector<int> area(n, 0); // 处理 q 次打扫 for (int i = 0; i < q; ++i) { int L, R, X; cin >> L >> R >> X; // 注意：题目中区域编号通常从 1 开始，而数组下标从 0 开始 // 所以需要转换为 [L-1, R-1] for (int j = L - 1; j <= R - 1; ++j) { area[j] += X; } } // 寻找最大值 int maxCleanliness = 0; for (int i = 0; i < n; ++i) { if (area[i] > maxCleanliness) { maxCleanliness = area[i]; } } // 输出结果 cout << maxCleanliness << endl; return 0; } ``` --- ## 🔍 代码说明 - **输入处理**： 第一行读入 `n` 和 `q`。 然后循环 `q` 次，每次读入 `L, R, X`。 - **区间加法**： 注意数组下标从 0 开始，题目中区域编号从 1 开始，因此将 `[L, R]` 转换为 `[L-1, R-1]`。 - **求最大值**： 遍历整个数组，用 `maxCleanliness` 记录最大值。 - **复杂度**： 最坏情况每次操作遍历整个数组，时间复杂度为 O(q * n)，这里 n ≤ 99，q 即使较大也能接受。 --- ## ✅ 测试示例 输入： ``` 5 3 1 3 2 2 4 3 3 5 1 ``` 过程： - 初始：[0,0,0,0,0] - 第1次：[2,2,2,0,0] - 第2次：[2,5,5,3,0] - 第3次：[2,5,6,4,1] 最大值 = 6 输出： ``` 6 ``` --- ## 🧠 扩展思考 如果 `n` 和 `q` 很大（例如 10^5 级别），就不能直接模拟了，需要使用 **差分数组 + 前缀和** 来优化到 O(n + q)。 差分数组做法： - 对于每次操作 `[L, R] + X`，我们只需： - `diff[L-1] += X` - `diff[R] -= X` - 最后对 `diff` 求前缀和，即可得到最终数组。 但本题 n ≤ 99，直接模拟更加简单易懂。 ######[AI问答 | 807点数解答 | 2026-06-21 19:33:03]