【GESP/CSP练习】GESP五级 / CSP-J 题解：luogu-P1090 [NOIP2004 提高组] 合并果子

NOIP 2004 提高组经典算法题，洛谷 P1090「合并果子」（对应 USACO 经典题 Fence Repair）。本题是算法竞赛与等级考试中**贪心算法（Greedy Algorithm）与优先队列（堆，Heap）的开山典范与试金石，标准收录于 CCF GESP 五级考纲（基础贪心算法与优先队列/堆考点）以及 CSP-J/S 必做经典题单。题目核心考查如何将多对象两两合并的最优化问题，映射到经典的哈夫曼树（Huffman Tree / 最优二叉树）**结构，通过微扰交换法证明每一步“必取当前最小两堆合并”的贪心选择性质，并依托高效的数据结构将合并的时间复杂度严格压缩至 $\mathcal{O}(n \log n)$ 。题目难度⭐⭐⭐☆☆，洛谷官方难度评级为普及-。

luogu-P1090 [NOIP2004 提高组] 合并果子

🔗 洛谷原题传送门：luogu-P1090 [NOIP2004 提高组] 合并果子

题目描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 $n-1$ 次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 $1$ ，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 $3$ 种果子，数目依次为 $1$ ， $2$ ， $9$ 。可以先将 $1$ 、 $2$ 堆合并，新堆数目为 $3$ ，耗费体力为 $3$ 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 $12$ ，耗费体力为 $12$ 。所以多多总共耗费体力 $=3+12=15$ 。可以证明 $15$ 为最小的体力耗费值。

输入格式

共两行。
第一行是一个整数 $n(1\leq n\leq 10000)$ ，表示果子的种类数。

第二行包含 $n$ 个整数，用空格分隔，第 $i$ 个整数 $a_i(1\leq a_i\leq 20000)$ 是第 $i$ 种果子的数目。

输出格式

一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 $2^{31}$ 。

输入输出样例

输入 #1

Code 2 行

13 
21 2 9

输出 #1

Code 1 行

说明/提示

对于 $30\%$ 的数据，保证有 $n \le 1000$ ：

对于 $50\%$ 的数据，保证有 $n \le 5000$ ；

对于全部的数据，保证有 $n \le 10000$ 。

题目深度剖析

1. 数学建模与哈夫曼树映射

我们不妨把题目中的 $n$ 堆果子看作二叉树中的 $n$ 个叶子节点，每个叶子节点的权值对应初始果堆的重量 $a_i$ 。

每次选择两堆果子合并，相当于在树形结构中将两个节点作为左右子节点，共同构建出一个父节点，父节点的权值即为两子节点权值之和（代表本次合并消耗的体力与合并后的新果堆重量）。经过 $n-1$ 次合并后，所有的叶子节点最终汇聚成为一棵以最终合并成果堆为根节点的完整二叉树。

假设第 $i$ 堆初始果子在最终二叉树中所处的深度为 $d_i$ （定义根节点的深度为 $0$ ）：

深度 $d_i$ 恰好代表了第 $i$ 堆果子在整个合并历史中被累加计算的总次数。
因此，合并所有果子所消耗的总精力，可以用经典的**带权路径长度（WPL, Weighted Path Length）**精确表示： $\text{Total Cost} = \sum_{i=1}^{n} a_i \times d_i$

这就将“最小化总体力消耗”的问题，彻底等价转化为计算机科学中极具里程碑意义的经典问题——构造一棵包含给定权值叶子节点的哈夫曼树（最优二叉树），使得带权路径长度 $\text{WPL}$ 达到全局最小。

2. 贪心选择性质与微扰法证明

构造哈夫曼树的核心法则即为贪心算法：每次合并均挑出当前所有堆中权值最小的两堆进行合并。

为什么这种局部最优选择必然能导向全局最优解？我们可以通过**微扰交换论证法（Exchange Argument）**给出严格的数学证明：

贪心选择性质（Greedy Choice Property）：
- 设当前集合中权值最小的两堆果子分别为 $x$ 与 $y$ ，不妨设 $x \le y$ 。
- 假设存在某个全局最优合并方案 $T$ ，其中 $x$ 和 $y$ 并不都在最深层作为兄弟节点合并。
- 在最优二叉树 $T$ 中，必然存在某对位于最深层的兄弟叶子节点 $u$ 和 $v$ （其深度满足 $d_u = d_v = \max_k d_k$ ）。
- 根据定义，必然有 $x \le u$ 且 $y \le v$ 。
- 若我们将在最深层的节点 $u$ 与较浅层的节点 $x$ 交换位置，树的带权路径长度变化量为： $\Delta \text{WPL} = (x \cdot d_u + u \cdot d_x) - (x \cdot d_x + u \cdot d_u) = (x - u)(d_u - d_x)$
- 因为 $d_u \ge d_x$ 且 $x \le u$ ，所以 $(x - u) \le 0$ 且 $(d_u - d_x) \ge 0$ ，故 $\Delta \text{WPL} \le 0$ 。
- 交换后新的树消耗体力不会增加，甚至可能更小！
- 同理，将 $v$ 与 $y$ 交换位置，带权路径长度同样不会增加。
- 这充分证明：必然存在一个最优解，其中最小的两堆果子位于最深层并且互为兄弟节点首先合并。
最优子结构（Optimal Substructure）：
- 当我们把权值最小的两堆 $x, y$ 合并为权值为 $x+y$ 的新堆后，消耗体力为 $x+y$ ；
- 剩余问题变为在包含新堆在内的 $n-1$ 堆果子中继续求最小合并体力。根据二叉树子树递归性质，原问题的最优解严格依赖于合并后子问题的最优解。

综上所述，每一步无脑合并最小的两堆果子，能够毫无悬念地达到全局最优。

3. 数据结构选型与算法对比

解决本题的核心矛盾在于：每次合并后都会产生一个全新的权值，我们需要在不断动态变化的集合中极速获取当前的全局最小值。

算法 1：朴素数组排序（初学者易错思路）
- 每合并一次，重新调用 sort 排序，或者用插入排序将新元素插回有序数组。
- $n-1$ 次合并，每次维护有序序列需 $\mathcal{O}(n)$ ，总时间复杂度为 $\mathcal{O}(n^2)$ 。
- 当 $n = 10000$ 时， $n^2 = 10^8$ 次运算，在 1 秒时限内极度边缘甚至直接超时（TLE），无法作为满分标程。
算法 2：STL 优先队列 / 小顶堆（推荐标准解法，GESP 五级 / CSP-J 核心）
- 利用二叉小顶堆（std::priority_queue<long long, vector<long long>, greater<long long>>）动态维护集合。
- 将 $n$ 个数全部插入小顶堆，建堆时间复杂度为 $\mathcal{O}(n \log n)$ 。
- 进行 $n-1$ 轮合并：每轮执行两次 top() + pop() 取出最小两项，相加后通过 push() 放回堆中。每次堆调整仅需 $\mathcal{O}(\log n)$ 。
- 总时间复杂度严格为 $\mathcal{O}(n \log n)$ ，总基本操作步数仅约 $1.4 \times 10^5$ 次，耗时在毫秒级以内，代码简练优美且极其稳健。
算法 3：双单调队列优化（NOIP / CSP-S 进阶算法思维）
- 观察生成的果子重量序列：如果我们将初始数组从小到大排序放入队列 $Q_1$ ；
- 每次合并得到的“新果堆”放入另一个队列 $Q_2$ 。
- 数学性质保证：由于每次合并的都是当前全集中的最小值，后合并出的新堆重量必然不小于先合并出的新堆重量，因此队列 $Q_2$ 内部的元素天然单调递增！
- 每一轮只需从 $Q_1$ 和 $Q_2$ 队头比较取最小值，单次操作 $\mathcal{O}(1)$ ，整体合并仅需 $\mathcal{O}(n)$ 。结合初始排序后总时间复杂度依然受制于排序的 $\mathcal{O}(n \log n)$ （若使用计数排序甚至可达到全流程 $\mathcal{O}(n + \max A)$ ）。这一双单调队列思想正是后续信奥名题「NOIP 蚯蚓」的核心灵魂。

4. 易错点与边界防坑指南

大顶堆与小顶堆的混淆：
- C++ STL 的 priority_queue<long long> 默认是大顶堆（优先弹出最大值）。
- 本题必须显式传入三个模板参数：priority_queue<long long, vector<long long>, greater<long long>> 才能正确初始化为小顶堆。
整型溢出防范：
- 尽管洛谷题面给出了“输入数据保证这个值小于 $2^{31}$ ”的提示，但若在极限数据下（例如构造特定退化的偏斜树），累加过程很容易触及甚至溢出 32 位有符号整型上限（约 $2.14 \times 10^9$ ）。
- 在竞赛与考级中，涉及累加代价的变量务必统一采用 long long 声明，坚决杜绝溢出风险。
$n = 1$ 的边界情况：
- 若果子一开始就只有 $1$ 堆，则完全不需要进行任何搬运合并，消耗体力为 $0$ 。
- 使用 while (pq.size() > 1) 作为循环条件，当 $n = 1$ 时循环体根本不会执行，直接输出初始值 total_cost = 0，逻辑自然闭环。

5. 复杂度深入分析

时间复杂度：
- 将 $n$ 个数全部推入优先队列耗时 $\mathcal{O}(n \log n)$ ；
- 循环合并 $n-1$ 次，每次执行 2 次堆弹出和 1 次堆插入，单次时间为 $\mathcal{O}(\log k)$ （ $k$ 为堆当前大小）；
- 总时间复杂度严格为 $\mathcal{O}(n \log n)$ 。代入 $n = 10000$ ， $n \log_2 n \approx 10000 \times 13.3 \approx 1.33 \times 10^5$ 次计算，在 $1.0\text{s}$ 时限内仅需约 $3\text{ms}$ ，秒级通过。
空间复杂度：
- 优先队列中最多同时存放 $n$ 个元素，额外空间复杂度为 $\mathcal{O}(n)$ ，占用内存小于 $1\text{MB}$ ，远低于题目限制。

完整参考代码 (C++11)

C++ 55 行

1/**
2 * Problem: luogu-P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G
3 * Algorithm: 贪心算法 (Greedy) / 优先队列 (Min-Heap / std::priority_queue) / 哈夫曼树 (Huffman Tree)
4 * Standard: C++11 (CCF GESP 官方大纲规范)
5 * Author: OneCoder
6 */
7
8#include <iostream>
9#include <vector>
10#include <queue>
11
12using namespace std;
13
14int main() {
15    int n;
16    cin >> n;
17
18    // 使用小顶堆（优先队列）维护当前所有果子堆的重量
19    // greater<long long> 表示堆顶始终保持当前所有元素中的最小值
20    priority_queue<long long, vector<long long>, greater<long long>> pq;
21
22    // 读取 n 堆果子的初始重量并依次压入小顶堆中
23    for (int i = 0; i < n; ++i) {
24        long long x;
25        cin >> x;
26        pq.push(x);
27    }
28
29    // 记录合并果子总共消耗的最小体力
30    long long total_cost = 0;
31
32    // 每次合并必定选出当前最小的两堆果子（贪心策略 / 哈夫曼树构建过程）
33    // 经过 n - 1 次合并后，优先队列中最终只剩下 1 堆果子
34    while (pq.size() > 1) {
35        // 取出当前重量最小的第一堆
36        long long first = pq.top();
37        pq.pop();
38
39        // 取出当前重量最小的第二堆
40        long long second = pq.top();
41        pq.pop();
42
43        // 两堆合并所消耗的体力等于两堆重量之和
44        long long merged = first + second;
45        total_cost += merged;
46
47        // 将合并生成的新果子堆放回小顶堆中，参与后续的合并
48        pq.push(merged);
49    }
50
51    // 输出最小总体力消耗值（若 n = 1，无需合并，输出 0）
52    cout << total_cost << endl;
53
54    return 0;
55}

C++ 算法考级专栏