C++ 实现洛谷 P3688 绝对值之和计算

### 📖题目理解 “P3688 绝对值之和” 通常是指洛谷上的一道题目。题目大意可能是给定一个序列，要求计算某些元素之间的绝对值之和。一般形式可能是对于序列 \(a_1,a_2,\cdots,a_n\)，计算 \(\sum_{1\leq i < j\leq n}|a_i - a_j|\) 之类的式子。 ### 💡解题思路 可以通过排序的方法来简化绝对值的计算。假设序列已经排序，即 \(a_1\leq a_2\leq\cdots\leq a_n\)，那么对于\(\sum_{1\leq i < j\leq n}|a_i - a_j|\)，可以重写为\(\sum_{j = 2}^{n}\sum_{i = 1}^{j - 1}(a_j - a_i)\)，进一步展开得到\(\sum_{j=2}^{n}((j - 1)a_j-\sum_{i = 1}^{j - 1}a_i)\)。 ### 📝C++ 代码实现 ```cpp #include <iostream> #include <algorithm> #include <vector> using namespace std; typedef long long ll; // 由于结果可能很大，使用 long long 类型 int main() { int n; cin >> n; // 输入序列的长度 vector<ll> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; // 输入序列的每个元素 } // 对序列进行排序 sort(a.begin(), a.end()); ll sum = 0; // 用于存储绝对值之和 ll prefix_sum = 0; // 前缀和 for (int j = 1; j < n; ++j) { prefix_sum += a[j - 1]; // 更新前缀和 sum += (j * a[j] - prefix_sum); // 计算当前位置的绝对值之和并累加到结果中 } cout << sum << endl; // 输出最终结果 return 0; } ``` ### 代码解释 1. **输入部分**：首先读取序列的长度 `n`，然后读取序列的每个元素并存储在向量 `a` 中。 2. **排序部分**：使用 `sort` 函数对序列进行排序，确保元素按升序排列。 3. **计算部分**：遍历排序后的序列，使用前缀和 `prefix_sum` 来加速计算。对于每个位置 `j`，计算 \((j * a[j] - prefix_sum)\) 并累加到结果 `sum` 中。 4. **输出部分**：输出最终的绝对值之和。 ######[AI问答 | 637点数解答 | 2026-07-19 17:04:16]