合并果子

题目描述

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

思路

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

参考代码

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
24
25
26
27
28
29
30
31#!/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-02 05:51
# update_at: 2026-10-02 05:51

import sys
from heapq import heapify, heappop, heappush


def huffman_total(weights: list[int]) -> int:
    """n-1 次两两合并的最小总代价：每次取当前最小的两堆合并（哈夫曼合并）。"""
    heapify(weights)
    cost = 0
    for _ in range(len(weights) - 1):
        merged = heappop(weights) + heappop(weights)  # 最小的两堆合成新堆
        cost += merged                                # 新堆里的每个果子都要再搬一次
        heappush(weights, merged)
    return cost


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    weights = [next(data) for _ in range(n)]  # 每种果子的数目，即各堆初始重量
    print(huffman_total(weights))


if __name__ == "__main__":
    solve()

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/**
 * 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 13:27
 * update_at: 2026-10-06 13:28
 */
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

typedef long long ll;

const int MAXN = 10005;

ll a[MAXN]; // a[i] 表示第 i 种果子的数目（堆的重量）
int n;

// 小根堆：每次取出当前最小的两堆合并
priority_queue<ll, vector<ll>, greater<ll> > heap;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        heap.push(a[i]);
    }

    // 哈夫曼贪心：每次合并最小的两堆，代价累加
    // 注意代价总和可能超过 int 范围，用 ll 累加
    ll ans = 0;
    for (int i = 1; i < n; i++) {
        ll x = heap.top(); heap.pop(); // 当前最小的一堆
        ll y = heap.top(); heap.pop(); // 当前次小的一堆
        ans += x + y;
        heap.push(x + y);
    }

    printf("%lld\n", ans);
    return 0;
}

目录

题目描述

思路

参考代码