合并果子

题目描述

$n$ 堆果子每次选两堆合并（代价为两堆重量和），求合并成一堆的最小总代价（ $n \le 10000$ ）。

思路

总代价等于各堆重量乘其合并树深度，重量小的应尽量深，故贪心每次合并当前最轻两堆；用小根堆维护，弹出两个最小值合并后压回并累加代价。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19from heapq import heapify, heappop, heappush


def main() -> None:
    data = open(0).read().split()
    n = int(data[0])
    heap = [int(x) for x in data[1:1 + n]]
    # 哈夫曼合并：每次取出最小的两堆合并，代价累加；小根堆维护
    heapify(heap)
    total = 0
    for _ in range(n - 1):
        a = heappop(heap)
        b = heappop(heap)
        total += a + b
        heappush(heap, a + b)
    print(total)


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
35
36
37
38
39
40
41/**
 * 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-06 11:32
 * update_at: 2026-10-06 11:32
 */
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

typedef long long ll;

int n;
ll total; // 最小总代价

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

    cin >> n;
    priority_queue<ll, vector<ll>, greater<ll> > pq; // 小根堆维护当前各堆重量
    for (int i = 1; i <= n; ++i) {
        ll x;
        cin >> x;
        pq.push(x);
    }

    // 每次取出最小的两堆合并，代价累加；共 n-1 次合并
    for (int i = 1; i <= n - 1; ++i) {
        ll a = pq.top(); pq.pop();
        ll b = pq.top(); pq.pop();
        ll c = a + b;
        total += c;
        pq.push(c);
    }

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

目录

题目描述

思路

参考代码