C++实现果子合并问题的最小体力消耗计算

### 🍎问题分析 本题的核心是要将不同堆的果子合并成一堆，每次合并两堆果子的体力消耗为两堆果子重量之和，目标是设计合并顺序使得总体力消耗最小。可以使用贪心算法，借助优先队列（小顶堆）来实现。每次从队列中取出重量最小的两堆果子进行合并，将合并后的新堆重新加入队列，重复这个过程直到队列中只剩下一堆果子。 ### 💻代码实现 ```cpp #include <iostream> #include <queue> #include <vector> using namespace std; int main() { int n; cin >> n; // 定义一个小顶堆 priority_queue<int, vector<int>, greater<int>> pq; // 读入每种果子的数目，并加入优先队列 for (int i = 0; i < n; ++i) { int ai; cin >> ai; pq.push(ai); } int total_cost = 0; // 当队列中元素大于1时，继续合并 while (pq.size() > 1) { // 取出重量最小的两堆果子 int a = pq.top(); pq.pop(); int b = pq.top(); pq.pop(); // 计算本次合并的体力消耗 int cost = a + b; total_cost += cost; // 将合并后的新堆加入队列 pq.push(cost); } // 输出最小体力耗费值 cout << total_cost << endl; return 0; } ``` ### 📝代码解释 1. **优先队列的使用**：`priority_queue<int, vector<int>, greater<int>> pq;` 定义了一个小顶堆，其中 `greater<int>` 表示队列中的元素按照从小到大的顺序排列。 2. **元素入队**：通过循环将每种果子的数目读入，并加入优先队列。 3. **合并过程**：只要队列中元素个数大于 1，就取出重量最小的两堆果子进行合并，计算合并的体力消耗并累加到总消耗中，然后将合并后的新堆重新加入队列。 4. **输出结果**：最后输出总体力消耗值。 ### ⚙️复杂度分析 - **时间复杂度**：每次合并操作需要 $O(log n)$ 的时间，总共需要进行 $n - 1$ 次合并，因此总的时间复杂度为 $O(n log n)$。 - **空间复杂度**：主要是优先队列的空间开销，为 $O(n)$。 ### 💡开发建议 - **异常处理**：可以添加对输入数据的合法性检查，例如检查 `n` 是否在规定范围内，每种果子的数目是否为正数等。 - **代码复用**：将合并果子的逻辑封装成一个函数，提高代码的复用性。 - **性能优化**：对于大规模数据，可以考虑使用更高效的数据结构或算法。 ### 📚学习资源 - [C++ 优先队列官方文档](https://en.cppreference.com/w/cpp/container/priority_queue) - 《算法导论》：经典的算法书籍，深入讲解了各种算法的原理和实现。 ######[AI写代码神器 | 743点数解答 | 2026-07-26 14:41:29]