区间修改求最大值：C++暴力与差分数组实现对比

根据问题描述，这是一个典型的区间更新并求最大值的问题。由于n和q最大为99，数据量很小，可以直接使用差分数组或暴力遍历来解决。这里提供两种C++解法。 ## 解法一：直接模拟（暴力遍历） 对每次打扫，遍历区间 `[Li, Ri]` 并将对应区域加上 `xi`，最后找出最大值。 ```cpp #include <iostream> using namespace std; int main() { int n, q; cin >> n >> q; int clean[100] = {0}; // 区域干净度数组，索引1到n 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++) { if (clean[i] > maxClean) { maxClean = clean[i]; } } cout << maxClean << endl; return 0; } ``` ## 解法二：差分数组优化 先构建差分数组，完成所有区间更新后，再前缀和还原每个区域的干净度，最后找最大值。 ```cpp #include <iostream> using namespace std; int main() { int n, q; cin >> n >> q; int diff[101] = {0}; // 差分数组，多一个位置用于边界处理 for (int i = 0; i < q; i++) { int L, R, x; cin >> L >> R >> x; diff[L] += x; diff[R + 1] -= x; // 注意R+1可能等于n+1，但数组大小设为101足够 } int clean[100] = {0}; int maxClean = 0; for (int i = 1; i <= n; i++) { clean[i] = clean[i - 1] + diff[i]; if (clean[i] > maxClean) { maxClean = clean[i]; } } cout << maxClean << endl; return 0; } ``` ## 代码解析 **解法一**： - 使用一个数组 `clean` 记录每个区域的干净度。 - 对每次打扫，用循环将 `[Li, Ri]` 范围内的每个元素增加 `xi`。 - 时间复杂度为 O(q * n)，对于 n<=99 完全足够。 - 空间复杂度 O(n)。 **解法二**： - 使用差分数组 `diff`，区间更新时只需修改两个位置：`diff[L] += x` 和 `diff[R+1] -= x`。 - 所有更新完成后，通过前缀和 `clean[i] = clean[i-1] + diff[i]` 还原真实值。 - 时间复杂度为 O(q + n)，更高效。 - 注意差分数组需要多开一个位置，防止越界。 两种解法均能正确输出结果，对于本题输入样例输出为 `3`。 ######[AI问答 | 704点数解答 | 2026-08-09 10:09:44]