优化代码解决超时问题：计算数组 f(l, r) 最小和

💡原代码之所以会超时（TLE），是因为使用了全排列的方法，其时间复杂度达到了 $O(n! \times n^3)$ ，当 $n$ 较大时，这个复杂度会导致程序运行时间过长。我们可以采用贪心算法来优化，将数组 `a` 按从小到大排序，数组 `b` 按从大到小排序，然后计算一次 `f(l, r)` 的和，这样时间复杂度可以优化到 $O(n^2)$ 。 以下是优化后的代码： ```cpp #include <iostream> #include <vector> #include <algorithm> const int MOD = 998244353; // 计算 f(l, r) 函数 long long f(const std::vector<int>& a, const std::vector<int>& b, int l, int r) { long long res = 0; for (int i = l; i <= r; ++i) { res = (res + (long long)a[i] * b[i]) % MOD; } return res; } // 计算所有 f(l, r) 的和 long long calculateSum(const std::vector<int>& a, const std::vector<int>& b) { int n = a.size(); long long sum = 0; for (int l = 0; l < n; ++l) { for (int r = l; r < n; ++r) { sum = (sum + f(a, b, l, r)) % MOD; } } return sum; } int main() { int n; std::cin >> n; std::vector<int> a(n), b(n); for (int i = 0; i < n; ++i) { std::cin >> a[i]; } for (int i = 0; i < n; ++i) { std::cin >> b[i]; } // 对 a 数组从小到大排序 std::sort(a.begin(), a.end()); // 对 b 数组从大到小排序 std::sort(b.begin(), b.end(), std::greater<int>()); long long minSum = calculateSum(a, b); std::cout << minSum << std::endl; return 0; } ``` ### 代码解释： 1. **输入处理**：读取数组 `a` 和 `b` 的长度 `n` ，并分别读取数组 `a` 和 `b` 的元素。 2. **排序操作**：将数组 `a` 按从小到大排序，数组 `b` 按从大到小排序。这样做的原因是，为了使 `f(l, r)` 的和最小，我们希望较小的 `a[i]` 与较大的 `b[i]` 相乘。 3. **计算和**：调用 `calculateSum` 函数计算排序后数组 `a` 和 `b` 的所有 `f(l, r)` 的和。 4. **输出结果**：输出计算得到的最小和。 ### 复杂度分析： - **时间复杂度**：排序的时间复杂度为 $O(n log n)$ ，计算 `f(l, r)` 的和的时间复杂度为 $O(n^2)$ ，因此总的时间复杂度为 $O(n^2)$ 。 - **空间复杂度**：主要使用了两个长度为 `n` 的数组，因此空间复杂度为 $O(n)$ 。 ######[AI问答 | 821点数解答 | 2026-05-10 16:15:59]