优化代码解决 TLE 问题：从 $O(n^3)$ 到 $O(n^2)$

这段代码出现 TLE（Time Limit Exceeded，超时）的原因在于其时间复杂度较高，原代码使用了三重嵌套循环，时间复杂度达到了 $O(n^3)$，在数据规模较大时会运行很慢。可以通过优化计算区间代价的方式，将时间复杂度优化到 $O(n^2)$。 ### 优化思路 在原代码中，计算区间 `[l, r]` 内元素变为 `a[r]` 的代价时，使用了一个循环来累加差值，这部分可以通过前缀和来优化。先计算数组的前缀和，这样在计算区间代价时就可以直接通过前缀和相减得到，避免了每次都进行循环累加。 ### 优化后的代码 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; // 主函数 int main() { int n, k; // 读取数组元素数量 n 和允许的操作次数 k cin >> n >> k; vector<int> a(n); // 读取数组元素 for (int i = 0; i < n; ++i) { cin >> a[i]; } // 对数组进行排序 sort(a.begin(), a.end()); // 计算前缀和 vector<long long> prefixSum(n + 1, 0); for (int i = 0; i < n; ++i) { prefixSum[i + 1] = prefixSum[i] + a[i]; } int maxCount = 0; int resultNumber = 0; // 遍历数组 for (int r = 0; r < n; ++r) { for (int l = 0; l <= r; ++l) { // 计算将区间 [l, r] 内的元素都变为 a[r] 所需的操作次数 long long cost = (long long)(r - l + 1) * a[r] - (prefixSum[r + 1] - prefixSum[l]); // 如果操作次数不超过 k if (cost <= k) { int currentCount = r - l + 1; // 更新最大出现次数和对应的数字 if (currentCount > maxCount || (currentCount == maxCount && a[r] < resultNumber)) { maxCount = currentCount; resultNumber = a[r]; } } } } // 输出结果 cout << maxCount << " " << resultNumber << endl; return 0; } ``` ### 代码解释 1. **前缀和计算**：通过 `prefixSum` 数组计算数组 `a` 的前缀和，`prefixSum[i]` 表示数组 `a` 前 `i` 个元素的和。 2. **区间代价计算**：使用前缀和计算将区间 `[l, r]` 内的元素都变为 `a[r]` 所需的操作次数，公式为 `(r - l + 1) * a[r] - (prefixSum[r + 1] - prefixSum[l])`。 3. **更新结果**：如果操作次数不超过 `k`，则更新最大出现次数和对应的数字。 ### 复杂度分析 - **时间复杂度**：$O(n^2)$，因为使用了两层嵌套循环。 - **空间复杂度**：$O(n)$，主要用于存储前缀和数组。 ######[AI问答 | 814点数解答 | 2026-04-04 20:10:30]