[NOIP 2004 提高组] 合并果子

题意

有 n 堆果子，每次选两堆合并，消耗体力等于这两堆重量之和。问怎样安排合并顺序，才能让总消耗最小。

思路

先看一个可以直接验证想法的朴素解：

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#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll INF = (1LL << 60);

map<vector<ll>, ll> memo;

ll dfs(vector<ll> a) {
    if (a.size() == 1) {
        return 0;
    }
    sort(a.begin(), a.end());

    map<vector<ll>, ll>::iterator it = memo.find(a);
    if (it != memo.end()) {
        return it->second;
    }

    ll ans = INF;
    int n = (int) a.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            vector<ll> nxt;
            for (int k = 0; k < n; k++) {
                if (k == i || k == j) {
                    continue;
                }
                nxt.push_back(a[k]);
            }
            nxt.push_back(a[i] + a[j]);
            ans = min(ans, dfs(nxt) + a[i] + a[j]);
        }
    }

    memo[a] = ans;
    return ans;
}

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

    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    memo.clear();
    cout << dfs(a) << '\n';
    return 0;
}

暴力会枚举下一次合并哪两堆，状态数增长很快，只适合小数据。

关键结论是：每次都合并当前最小的两堆，一定存在最优解。任意合并方案都可以看成一棵二叉合并树，叶子是原来的果子堆；某堆果子的重量会被累计多少次，取决于它在树中的深度。越深的叶子会被加得越多，所以重量小的果子更适合放到更深的位置。

在最优合并树里，最深的两个叶子可以看成兄弟。如果这两个位置不是当前最小的两堆，把最小的两堆换过去不会让总代价变大。因此第一步可以先合并最小的两堆，合并后把新堆当成一个整体，继续做同样的问题。

实现时维护一个小根堆：

把所有果子堆放进堆；
每次弹出两个最小值；
把它们的和加入答案，再压回堆；
重复到只剩一堆。

如果先把果子堆排序，还可以用两个普通队列模拟出同样的贪心效果：

q1 按从小到大的顺序装下原来的果子堆；
q2 装合并产生的新堆；
每次取两个最小值时，只需要比较 q1 和 q2 的队首，弹出较小的那个；
合并出的新堆放进 q2 队尾。

新堆 x+y 一定不小于上一个放进 q2 的堆，因为每次取出的都是当时的全局最小值，所以 q2 天然保持单调递增，不需要再排序。排序是 $O(n\log n)$ ，之后每次合并只是两次队首比较，合并阶段总共 $O(n)$ 。

Python 知识

heapq.heapify(heap) 可以把列表原地变成小根堆。
heapq.heappop 每次弹出当前最小值，heapq.heappush 把新堆放回去。
本题输入全是整数，换行没有特殊含义，适合用 sys.stdin.buffer.read().split() 一次读完。

C++ 中常用 priority_queue<int, vector<int>, greater<int>> 表示小根堆；Python 直接用 heapq 操作普通列表即可。

代码

Python 小根堆写法：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24import heapq
import sys


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    heap = data[1:1 + n]

    heapq.heapify(heap)
    answer = 0

    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        merged = a + b
        answer += merged
        heapq.heappush(heap, merged)

    print(answer)


if __name__ == "__main__":
    main()

C++ 优先队列写法：

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#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

    int n;
    cin >> n;

    priority_queue<ll, vector<ll>, greater<ll> > pq;
    for (int i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        pq.push(x);
    }

    ll ans = 0;
    while (pq.size() > 1) {
        ll a = pq.top();
        pq.pop();
        ll b = pq.top();
        pq.pop();

        ll sum = a + b;
        ans += sum;
        pq.push(sum);
    }

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

C++ 排序 + 双队列写法：

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72/**
 * 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-05 10:12
 * update_at: 2026-09-05 10:12
 */
// main-queue.cpp：排序 + 双队列写法，合并阶段 O(n)，不依赖堆。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 10005;

int n;
ll a[MAXN];      // 读入的 n 堆果子，排序后进入 q1
queue<ll> q1;    // 装排好序的原始果子堆，队首最小
queue<ll> q2;    // 装合并产生的新果子堆，天然单调递增
ll ans;          // 总消耗的体力

// 取出当前全局最小的那堆：只可能来自两个队列的队首。
ll take_min() {
    if (q1.empty()) {          // q1 取空后，只能从 q2 取
        ll v = q2.front();
        q2.pop();
        return v;
    }
    if (q2.empty()) {          // q2 还没有新堆
        ll v = q1.front();
        q1.pop();
        return v;
    }
    if (q1.front() <= q2.front()) {
        ll v = q1.front();
        q1.pop();
        return v;
    }
    ll v = q2.front();
    q2.pop();
    return v;
}

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

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

    // 原始堆先排序：之后 q1 从队首到队尾严格递增。
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        q1.push(a[i]);
    }

    // 合并 n-1 次，每次都取当前最小的两堆。
    // 新堆 x+y 一定 >= 上一个放进 q2 的新堆，
    // 所以 q2 保持单调递增，新堆直接放队尾即可。
    for (int i = 1; i <= n - 1; i++) {
        ll x = take_min();
        ll y = take_min();
        ll sum = x + y;
        ans += sum;
        q2.push(sum);
    }

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

复杂度

小根堆写法一共合并 n-1 次，每次堆操作复杂度为 $O(\log n)$ ，所以时间复杂度是 $O(n \log n)$ ，空间复杂度是 $O(n)$ 。

排序 + 双队列写法中，排序是 $O(n\log n)$ ，合并阶段 $O(n)$ ，总时间复杂度同样是 $O(n\log n)$ ；空间复杂度是 $O(n)$ ，但代码里没有堆，常数更小，输入接近有序时优势更明显。

总结

这题是 Huffman 贪心模板：反复合并当前最小的两堆。Python 里记住 heapq 这组小根堆函数即可。

[NOIP 2004 提高组] 合并果子

目录

题意

思路

Python 知识

代码

复杂度

总结