C++ 算法题：合并苹果袋 (无 VECTOR 头文件)

唐僧师徒四人准备去卖苹果换盘缠，现在已经打包成了许多袋。孙悟空决定让猪八戒把所有的苹果合成一袋。每一次合并，八戒可以把两袋苹果合并到一起，消耗的体力等于两袋苹果的重量之和。可以看出，所有的苹果经过 n-1 次合并之后，就只剩下一袋了。八戒在合并苹果时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些苹果搬到集市，所以八戒在合并苹果时要尽可能地节省体力。你的任务是设计出合并的次序方案，使八戒耗费的体力最少，并输出这个最小的体力耗费值。

输入描述

输入文件名 apple.in

共两行，第一行是一个整数 n（1 <= n <= 10000），表示苹果的袋数。

第二行包含 n 个整数，用空格分隔，第 i 个整数 ai（1 <= ai <= 20000）是第 i 袋苹果的数目。

输出描述

输出文件名 apple.out

共一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 2^31。

样例1

输入

3
1 2 9

输出

15

提示

对于 30% 的数据，保证有 n <= 1000；

对于 50% 的数据，保证有 n <= 5000；

对于全部的数据，保证有 n <= 10000。

解题思路

这个问题可以使用贪心算法解决。贪心算法的思路是每次选择两袋苹果数目最小的两袋进行合并，然后将合并后的袋子放回袋子序列中，重复这个过程直到只剩下一袋苹果。

具体实现步骤

1. 读取输入的袋子数目 n 和每袋苹果数目的数组 a。
2. 将数组 a 按照从小到大的顺序排序。
3. 初始化总体力耗费值为 0。
4. 循环 n-1 次，每次选择数目最小的两袋苹果进行合并，并将合并后的袋子放回袋子序列中，更新总体力耗费值。
5. 输出总体力耗费值。

C++ 代码实现

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
int totalCost = 0;
for (int i = 0; i &lt; n-1; i++) {
    int cost = a[i] + a[i+1];
    totalCost += cost;
    a[i+1] = cost;
}

cout &lt;&lt; totalCost &lt;&lt; endl;

return 0;

}

通过以上代码，我们可以得到最小的体力耗费值。