题目描述

$n$ 堆果子，第 $i$ 堆重量为 $a_i$。每次合并两堆，体力为两堆重量之和；合并 $n-1$ 次后只剩一堆。求最小总体力。

输入：第一行 $n$（$1 \le n \le 30000$），第二行 $n$ 个整数 $a_i$（$1 \le a_i \le 20000$）。
输出：最小体力耗费值。

样例输入：

1
23
1 2 9

样例输出：

115

思路

每次合并的代价会作为新堆重量继续参与后续合并，因此越小的堆越早合并越优。用小根堆维护当前所有堆，每次取出最小的两堆合并，累加代价并把新堆放回，重复 $n-1$ 次即可。

下面是我的思路。先用"放大缩小"的方法看清小规模的规律，再从三个角度证明关键结论——每一步都合并当前最小的两堆。

先看特例：从小规模找规律

• 只有两堆（$n=2$）：只有一种合并方式，代价就是 $a+b$，不用思考。
• 三堆（$n=3$）：从小到大是 $a,b,c$，要合并两次。最后一次一定是把所有果子合成一堆，代价恒为总重 $a+b+c$，怎么选都逃不掉。所以总代价 = 第一次合并的代价 + $(a+b+c)$，想省钱只能让第一次尽量小——第一次合并 $a,b$。样例 $1,2,9$：$(1+2)+(1+2+9)=15$。
• 四堆（$n=4$）：写一个暴力程序验证（程序见下）——每次任选两堆合并，递归到底，枚举出所有合并过程的总代价。对 $1,2,3,4$，全部 18 种合并过程的代价在 19 ~ 26 之间，最小的 19 正是"先合并最小两堆 1、2"得到的：$3+6+10=19$。随机数据对拍 $n=2 \sim 7$，贪心也始终等于暴力最小值。

上面说的暴力程序就是 brute.cpp：每次任选两堆合并，递归到底，把所有合并顺序的总代价排序输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-12
 * update_at: 2026-10-12
 *
 * 暴力程序：枚举所有合并顺序，验证"先合并最小的两堆"最优
 * 只能跑很小的 n（合并顺序有 (2n-3)!! 种，n=7 就有 10395 种）
 */

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 10;      // 暴力只能处理很少的堆数
const int MAXC = 100000;  // 最多记录这么多种合并顺序

ll a[MAXN];       // 一开始各堆的重量
ll all[MAXC];     // 所有合并顺序的总代价
int alln;         // 总代价的个数

// 枚举 cur[0..cnt-1] 这 cnt 堆的所有合并顺序
// cost 是已经花掉的体力
void dfs(ll cur[], int cnt, ll cost) {
    if (cnt == 1) {           // 只剩一堆，一种合并顺序走完了
        all[alln++] = cost;   // 记录这种顺序的总代价
        return;
    }
    int i, j, k;
    for (i = 0; i < cnt; ++i)        // 任选两堆 i,j 合并
        for (j = i + 1; j < cnt; ++j) {
            ll b[MAXN];               // 合并后的新集合
            int m = 0;
            for (k = 0; k < cnt; ++k)
                if (k != i && k != j) b[m++] = cur[k];
            b[m++] = cur[i] + cur[j]; // i,j 两堆合并成一堆
            dfs(b, m, cost + cur[i] + cur[j]);
        }
}

int main() {
    int n, i;
    cin >> n;
    for (i = 0; i < n; ++i) cin >> a[i];

    alln = 0;
    dfs(a, n, 0);
    sort(all, all + alln);    // 按总代价从小到大排

    cout << "合并顺序共 " << alln << " 种, 总代价从小到大: " << endl;
    for (i = 0; i < alln; ++i) cout << all[i] << " ";
    cout << endl;
    cout << "最小总代价 = " << all[0] << endl;
    return 0;
}

输入 4 和 1 2 3 4 运行，它输出 18 种代价：19 20 20 ... 25 26，最小 19，正是先合并 1、2 的方案。

同样的暴力程序用 Python 写，用生成器 + yield from 可以短很多，输出完全一样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-12
# update_at: 2026-10-12
#
# 暴力程序(pythonic 短写法): 枚举所有合并顺序, 验证"先合并最小的两堆"最优
# 只能跑很小的 n (合并顺序有 (2n-3)!! 种, n=7 就有 10395 种)

from itertools import combinations


def dfs(cur, cost):
    """任选两堆合并, 生成器 yield 出每种合并顺序的总代价"""
    if len(cur) == 1:                     # 只剩一堆, 一种合并顺序走完
        yield cost
        return
    for i, j in combinations(range(len(cur)), 2):
        rest = [cur[k] for k in range(len(cur)) if k not in (i, j)]
        yield from dfs(rest + [cur[i] + cur[j]], cost + cur[i] + cur[j])


n = int(input())
a = list(map(int, input().split()))
costs = sorted(dfs(a, 0))                 # 所有合并顺序的总代价, 从小到大
print(f"合并顺序共 {len(costs)} 种, 总代价从小到大:")
print(*costs)
print("最小总代价 =", costs[0])

规律很明显了：每一步都合并当前最小的两堆。下面三种思路从不同角度证明它。

思路1：递归地考虑

定义 $f(S)$：把堆的集合 $S$ 全部合并成一堆的最小总代价。边界：只剩一堆时 $f=0$，只剩两堆时 $f(x,y)=x+y$。

一般情况，第一步任选两堆 $x,y$ 合并：付出 $x+y$ 的体力，同时它们变成重量 $x+y$ 的一堆新堆，问题就变成规模小 1 的同类问题：

以 $n=4$（$a \le b \le c \le d$）为例，第一步有 6 种选法，对应 6 个子问题：

1
2f(a+b, c, d)    f(a+c, b, d)    f(a+d, b, c)
f(b+c, a, d)    f(b+d, a, c)    f(c+d, a, b)

每个子问题只剩 3 堆，而 3 堆的最优值我们已经会算：

（第一步合并最小两数，第二步付出总重。）注意 $x+y+z$ 恒等于 $a+b+c+d$，6 个子问题的这部分完全一样。所以比较这 6 个子问题，其实只用比较"合并一次后，剩下三堆中最小两数之和谁最小"。

那么这 6 个子问题里面哪个一定最小呢？一定是第一个 $f(a+b,c,d)$——也就是说，先合并最小的两堆，一定不比别的选择差（严格证明见思路2，小规模数据也可以用暴力程序核实）。于是：

不管怎么拆这个问题，最优方案的第一步都是合并最小两堆，问题从 4 堆变成 3 堆；而 3 堆的答案同样是"先合并最小两堆"。$n=5$、$n=6$……同理：第一步合并最小两堆后，剩下的就是规模小 1 的同类问题。对堆数做数学归纳法，任意 $n$ 都成立——这正是"每步取最小两堆"的贪心算法。

本质是数学归纳法的思想: n+1 -> n 的这一步 一定是 选最小的两个

思路2：交换验证

不从递归入手，直接比较"谁该早合并"。

先记一个量：每堆果子被累加的次数 $d_i$，也就是它参与合并的次数（它所在的合并堆每被合并一次，它的重量就要算一次体力）。于是总代价可以写成：

交换1：轻的堆要更早合并。 假如某个方案里，轻堆 $a_i$ 的次数反而比重大堆 $a_j$ 少（$a_i < a_j$ 但 $d_i < d_j$），那么把这两堆果子的"名字"互换——合并的先后顺序完全不变，只是换了标签。新方案的总代价变化为：

总代价竟然变小了，与"最优方案"矛盾。所以最优方案里一定是：越轻的堆，被累加的次数越多，也就是合并得越早。

交换2：第一步就合并最小的两堆。 设最轻的两堆是 $a,b$，而某个最优方案第一步合并的是 $x,y$。第一步合并的两堆合并得最早，被累加的次数达到最大值（记作 $D$；"合并越早、次数越多"在思路3 的合并树里看得最清楚）。而由交换1，最轻的 $a,b$ 的次数不比任何一堆少，所以 $a,b$ 的次数也是 $D$。既然 $a,b,x,y$ 四堆的次数都是 $D$，把它们的名字两两对调，总代价毫无变化（乘的都是同一个 $D$）。对调之后，这个方案的第一步合并的就是 $a,b$。

结论：一定存在某个最优方案，第一步合并最小的两堆。

归纳收尾。 第一步合并 $a,b$ 之后，它们变成重量 $a+b$ 的一堆，问题变成 $n-1$ 堆的同类问题。对堆数 $n$ 归纳：$n=2$ 时显然；$n$ 堆时先合并最小两堆，剩下的由归纳假设继续"每步取最小两堆"就是最优。所以贪心算法从头到尾都是最优的。

回到思路1 的疑问：6 个子问题里 $f(a+b,c,d)$ 最小，正是交换2 的结论。

上面的这个思路是从合并的贡献考虑的. 不从贡献考虑:

两个序列

1
2
3a1 a2 a3 .... an
b1 b2 b3 .... bn

如果任意$a_i \leqslant b_i$ ,那么显然f(序列1) >= f(序列2). 直觉一定对.

那么序列a ,合并最小的两个值形成序列1,合并其它的两个值形成序列2

1
2a1+a2 , a3 ................ 序列1
a2+a3 , a1 ................ 序列2

显然序列2对应的数字都>=序列1. 证明完毕

思路3：哈夫曼树——把代价算清楚

每个合并过程都可以画成一棵二叉树（合并树）：每片叶子是原来的一堆果子（权值 $a_i$），每个内部节点是一次合并（节点权值 = 新堆重量 = 两个儿子权值之和），根是最后那堆。以样例 $1,2,9$ 为例：

1
2
3
4
5        12        ← 根：最后一次合并，代价 12
       /  \
      3    9      ← 第二次合并，代价 3；9 是原堆
     / \
    1   2         ← 第一次合并，代价 3

每次合并的体力就是内部节点的权值，所以这个合并的总代价有一个漂亮的公式：

其中 $d_i$ 是叶子 $i$ 到根的层数，正好等于它参与合并的次数——叶子的重量会被它到根路径上的每个内部节点各加一次，两种看法完全一致。样例验证：$3+12=15$，$1 \times 2 + 2 \times 2 + 9 \times 1 = 15$。

于是问题变成：给定叶子权值，怎么摆这棵二叉树，能让 $\sum a_i d_i$ 最小。这正是**哈夫曼树（哈夫曼编码）**要解决的问题：权值越大的叶子要摆得越浅，权值越小的叶子要摆得越深——和交换1"轻的堆合并得越早"一模一样。而"每次合并最小两堆"恰好把最轻的两片叶子放到最深的一对兄弟位置上，这正是哈夫曼树的构造方法。所以贪心 = 哈夫曼 = 最优。

三种思路各解决一件事：思路1 回答"问题怎么拆"，思路2 直接证明"先合并最小两堆不吃亏"，思路3 把代价算成公式，让"轻的放深处"一目了然。

参考代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 07:28
# update_at: 2026-09-30 07:28

import sys
from heapq import heapify, heappop, heappush
from itertools import islice


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    heaps = list(islice(data, n))          # 每种果子的数目
    heapify(heaps)                         # 小根堆：每次取最小的两堆合并

    cost = 0
    while len(heaps) > 1:                  # 还剩多堆就要再合并一次
        merged = heappop(heaps) + heappop(heaps)  # 最小的两堆合成新堆
        cost += merged                     # 本次体力 = 两堆重量之和
        heappush(heaps, merged)
    print(cost)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 12:13
 * update_at: 2026-10-05 12:13
 */

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

typedef long long ll;

const int MAXN = 30005;

ll a[MAXN]; // 每堆果子的重量

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    // 小根堆：每次取最小的两堆合并
    priority_queue<ll, vector<ll>, greater<ll> > q;
    for (int i = 1; i <= n; ++i) q.push(a[i]);

    ll ans = 0;
    while (q.size() > 1) {
        ll x = q.top(); q.pop();
        ll y = q.top(); q.pop();
        ll s = x + y;   // 合并新堆的重量
        ans += s;       // 本次耗费体力
        q.push(s);
    }

    cout << ans << "\n";
    return 0;
}