C++实现区间累加求最大值：差分法 vs 暴力模拟

好的，我们来一步步分析并解决这个“区间多次累加，求最大值”的问题。 ## 🧹 问题理解 我们有 `n` 个区域（编号从1到n），初始干净度都是0。 一共有 `q` 次打扫操作，每次操作会把区间 `[Li, Ri]` 内所有区域的干净度增加 `Xi`。 最终我们需要输出所有区域中 **最大的干净度值**。 --- ## ✅ 解题思路 题目中 `n <= 99` 非常小，我们可以直接用 **暴力模拟**，每次操作遍历区间更新，最后取最大值。复杂度为 `O(q * n)`，完全可行。 但为了更高效，我们可以使用 **差分数组 + 前缀和** 的方法，复杂度降为 `O(n + q)`。 这里用 C++ 实现时，推荐使用第二种方法，因为它更快且扩展性好。 --- ## 🚀 方法一：暴力模拟（推荐用于本题小数据） ### 🔧 实现步骤 1. 创建一个大小为 `n + 2` 的数组 `clean`，初始化为0。 2. 遍历 `q` 次操作，每次将 `clean[Li]` 到 `clean[Ri]` 都加上 `Xi`。 3. 遍历 `clean[1..n]`，找出最大值并输出。 ### 💻 代码实现 ```cpp #include <iostream> #include <algorithm> using namespace std; int main() { int n, q; cin >> n >> q; int clean[100] = {0}; // n <= 99，多开一点防止越界 for (int i = 0; i < q; i++) { int L, R, X; cin >> L >> R >> X; for (int j = L; j <= R; j++) { clean[j] += X; } } int maxClean = 0; for (int i = 1; i <= n; i++) { maxClean = max(maxClean, clean[i]); } cout << maxClean << endl; return 0; } ``` ### 📌 复杂度分析 - **时间复杂度**: `O(q * n)`，最坏 `99 * 99 ≈ 9801`，非常快。 - **空间复杂度**: `O(n)`。 --- ## ⚡ 方法二：差分数组 + 前缀和（推荐用于大数据） ### 🔧 实现步骤 1. 创建差分数组 `diff`，大小 `n + 2`，初始为0。 2. 对于每次操作 `[Li, Ri]` 加 `Xi`： `diff[Li] += Xi` `diff[Ri + 1] -= Xi` 3. 计算前缀和得到每个位置的实际干净度，同时记录最大值。 ### 💻 代码实现 ```cpp #include <iostream> #include <algorithm> using namespace std; int main() { int n, q; cin >> n >> q; int diff[102] = {0}; // 差分数组，n <= 99，多开一些空间 for (int i = 0; i < q; i++) { int L, R, X; cin >> L >> R >> X; diff[L] += X; diff[R + 1] -= X; } int maxClean = 0; int current = 0; for (int i = 1; i <= n; i++) { current += diff[i]; maxClean = max(maxClean, current); } cout << maxClean << endl; return 0; } ``` ### 📌 复杂度分析 - **时间复杂度**: `O(n + q)`，即使 `n` 和 `q` 都很大也能应对。 - **空间复杂度**: `O(n)`。 --- ## 🧠 关键概念解释 ### 📋 差分数组 差分数组 `diff[i]` 表示 `clean[i] - clean[i-1]` 的差值。 对区间 `[L, R]` 同时加 `X`，等价于 - `diff[L] += X` - `diff[R + 1] -= X` 之后，通过前缀和 `current += diff[i]` 即可还原出 `clean[i]` 的值。 ### 📋 前缀和 前缀和是指从数组第一个元素累加到当前位置的总和。差分数组还原时，`current` 就是当前位置的实际干净度。 --- ## ⚠️ 常见陷阱与注意事项 1. **数组越界**：差分法中 `diff[R+1]` 可能超出 `n`，所以要开大一点（如 `n+2`）。 2. **初始值**：题目说一开始所有区域干净度为0，无需额外初始化。 3. **输入格式**：注意 `Li` 和 `Ri` 是从1开始编号的，数组索引要对应好。 4. **多组测试**：如果题目有多个测试用例，记得每次清空数组。 --- ## 📚 学习资源推荐 - [差分数组与区间更新](https://oi-wiki.org/basic/difference/) - [前缀和与差分](https://www.cnblogs.com/xyqzzz/p/13895013.html) --- ## 🎯 开发建议 1. **优先选择差分法**：即使本题数据小，但养成使用差分法的习惯，能轻松应对更大数据规模。 2. **注意边界条件**：区间操作时，`Ri` 可能等于 `n`，`diff[Ri+1]` 要确保不会越界。 3. **善用 `std::max`**：C++标准库已经提供，避免自己写条件判断。 4. **代码可读性**：变量名清晰（如 `diff`，`current`），注释明确，方便日后维护。 --- 这个问题的核心就是 **区间批量加法 + 求全局最大值**，差分法是最优解。 ######[AI写代码神器 | 1328点数解答 | 2026-06-06 21:17:48]