区间加法后求最大干净度——C++差分与暴力解法

好的，这个问题本质上是多次区间加法后，求单点最大值。根据题目条件（`n <= 99`，`q` 未给出上限但总体很小），最简单的方案是用一个数组模拟每次加操作。 也可以用差分数组来加速运算，避免每次区间都循环。下面给出两种实现和对应注释。 --- ## 方法一：暴力模拟 每次操作直接用循环遍历 `[Li, Ri]` 区间，给每个位置增加 `Xi`。 最后用 `max` 找到最大值。 ```cpp #include <bits/stdc++.h> using namespace std; int main() { int n, q; cin >> n >> q; vector<int> clean(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) { clean[j] += X; } } int ans = *max_element(clean.begin() + 1, clean.end()); // 从1到n找最大 cout << ans << endl; return 0; } ``` 复杂度：**O(n × q)** 当 n = 99，q 即使达到几千也很快。 --- ## 方法二：差分数组优化 差分可以在 **O(n + q)** 时间内完成全部区间加法。 思路： - 差分数组 `diff`，`diff[L] += X`，`diff[R+1] -= X`。 - 最后求一次前缀和得到每个位置的干净度，同时记录最大值。 ```cpp #include <bits/stdc++.h> using namespace std; int main() { int n, q; cin >> n >> q; vector<int> diff(n + 2, 0); // 多开一位，防止R+1越界 for (int i = 0; i < q; ++i) { int L, R, X; cin >> L >> R >> X; diff[L] += X; diff[R + 1] -= X; } int ans = 0, cur = 0; for (int i = 1; i <= n; ++i) { cur += diff[i]; if (cur > ans) ans = cur; } cout << ans << endl; return 0; } ``` 复杂度：**O(n + q)**，只做了两次线性扫描。 --- 📌 **提示**： - 注意差分数组要 `+1` 的偏移，防止 R 到达 n 时越界。 - 输入范围很小，方法一完全可以接受；若 n 更大（如 10^5），必须使用方法二。 ######[AI问答 | 628点数解答 | 2026-05-14 18:48:37]