优化代码避免TLE：计算所有 f(l, r) 的和

这段代码的时间复杂度为 $O(n^2)$，在数据量较大时会超时（TLE）。可以通过优化计算所有 $f(l, r)$ 的和的过程来降低时间复杂度。 下面是优化后的代码： ```cpp #include <iostream> #include <vector> #include <algorithm> const int MOD = 998244353; // 计算所有 f(l, r) 的和 long long calculateSum(const std::vector<int>& a, const std::vector<int>& b) { int n = a.size(); std::vector<long long> c(n); // 计算 c[i] = a[i] * b[i] for (int i = 0; i < n; ++i) { c[i] = (long long)a[i] * b[i] % MOD; } long long sum = 0; // 计算每个 c[i] 在所有 f(l, r) 中出现的次数 for (int i = 0; i < n; ++i) { // 计算 c[i] 出现的次数 long long count = (long long)(i + 1) * (n - i) % MOD; sum = (sum + c[i] * count % MOD) % 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. **计算 $c[i] = a[i] * b[i]$**：首先计算 $c[i] = a[i] * b[i]$，存储在 `c` 数组中。 2. **计算每个 $c[i]$ 在所有 $f(l, r)$ 中出现的次数**：对于 $c[i]$，它在所有 $f(l, r)$ 中出现的次数为 $(i + 1) * (n - i)$。因为 $l$ 可以取 $0$ 到 $i$ 共 $i + 1$ 个值，$r$ 可以取 $i$ 到 $n - 1$ 共 $n - i$ 个值。 3. **计算所有 $f(l, r)$ 的和**：将每个 $c[i]$ 乘以它出现的次数，然后累加到 `sum` 中。 ### 复杂度分析 - **时间复杂度**：$O(n)$，主要是计算 $c[i]$ 和每个 $c[i]$ 出现的次数。 - **空间复杂度**：$O(n)$，主要是存储 $c$ 数组。 ######[AI问答 | 765点数解答 | 2026-05-10 16:19:03]