C++ 配对分组求最重船重问题解法

好的，我们先来分析一下这个问题。 ## 🧩 问题分析 题目要求**最重和最轻配对，次重和次轻配对**……所以我们的任务是： 1. 先对所有人的体重**排序**（从小到大）。 2. 然后遍历配对：第 `i` 个人 和 第 `n-1-i` 个人 一组（0-based 下标）。 3. 计算每一组的重量之和，找出其中的最大值。 这种配对方式是最简单的贪心策略（实际上也是最优的一种组合方式，保证最重的不会过度堆积）。 --- ## 💡 解题步骤 - **第一步**：读取 n（人数）。 - **第二步**：读取每个人的体重到数组（或 vector）。 - **第三步**：对数组进行**升序排序**。 - **第四步**：用两个指针： - 左指针 `i = 0` 指向最轻的 - 右指针 `j = n-1` 指向最重的 - 当 `i < j` 时，计算 `weight[i] + weight[j]`，更新最大和，然后 `i++`、`j--`。 - **第五步**：输出最大和。 因为 n 是偶数，所以每个都会配对，不会剩下单独一个人。 --- ## 🚀 C++ 实现 ```cpp #include <iostream> #include <vector> #include <algorithm> // std::sort using namespace std; int main() { int n; cin >> n; vector<int> weights(n); // 读取体重 for (int i = 0; i < n; ++i) { cin >> weights[i]; } // 按从小到大排序 sort(weights.begin(), weights.end()); int maxSum = 0; int left = 0; int right = n - 1; // 配对并找出最大和 while (left < right) { int sum = weights[left] + weights[right]; if (sum > maxSum) { maxSum = sum; } ++left; --right; } // 输出结果 cout << maxSum << endl; return 0; } ``` --- ## 📌 代码说明 - **`sort(weights.begin(), weights.end())`**：对体重进行升序排序，方便最轻和最重配对。 - **双指针遍历**：`left` 从最轻开始，`right` 从最重开始，每次计算这两个人的重量之和。 - **更新最大值**：每次配对后，如果当前的和大于之前的 `maxSum`，则更新。 - **循环终止条件**：`left < right`，因为人数是偶数，所以刚好配对完。 --- ## 🧪 测试样例验证 输入： ``` 8 2 8 3 7 1 4 5 7 ``` 排序后：`1 2 3 4 5 7 7 8` 配对： - (1, 8) → 9 - (2, 7) → 9 - (3, 7) → 10 - (4, 5) → 9 最大和 = **10** ✅ 输出： ``` 10 ``` --- ## 🛠️ 复杂度分析 - **时间复杂度**：排序 `O(n log n)`，配对过程 `O(n)`，总体是 `O(n log n)`，对 n<100 毫无压力。 - **空间复杂度**：`O(n)` 用于存储体重数组。 --- ## ⚠️ 常见注意事项 - **n 一定是偶数**，所以不用处理奇数情况。 - 如果体重范围很大，可以用 `long long` 存储求和结果，防止溢出（但本题 `n<100` 体重一般不大）。 - 题目保证输入合法，不用考虑异常输入。 --- ## 📚 延伸思考 这种“最重配最轻”的策略在很多类似问题（比如尽量平衡负载、最小化最大船重）中都很常用。它是一个**贪心思想**，在这种场景下是最优解，因为如果最重的和最重的在一起，船重必然更大，所以一定要让最重的和最轻的搭配才能压低最大值。 --- ######[AI写代码神器 | 931点数解答 | 2026-08-09 10:58:14]