OneCoder Avatar
OneCodercoderli.com · 1023 篇博文
⌘ NOIP

NOIP 全国联赛真题

🎨 视觉封面

【NOIP真题】2004 合并果子 luogu-P1090 | 适用于 GESP五级 / CSP-J 练习

📅 2026-09-22·✍️ OneCoder·计算中...·⏱️ 14 分钟

把散落的多堆果子合并成一堆,每次只能合并两堆,所耗体力等于两堆果子的重量之和——如何规划合并顺序以使总体力最小?洛谷 P1090 [NOIP2004 提高组]《合并果子》是计算机科学中霍夫曼编码(Huffman Coding)与最优二叉树模型在信息学竞赛中的最经典投影。每次贪心选取当前重量最小的两堆进行合并,不仅直观吻合贪心选择性质,其数学正确性更由拟阵与前缀码理论所严格保证。在工程实现上,配合 STL 优先队列(小根堆 priority_queue)或双队列线性归并,是 GESP 五级掌握贪心思想与高级数据结构的必经之路。

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

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

题目描述

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

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

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

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

输入格式

共两行。
第一行是一个整数 ,表示果子的种类数。

第二行包含 个整数,用空格分隔,第 个整数 是第 种果子的数目。

输出格式

一个整数,也就是最小的体力耗费值。输入数据保证这个值小于 。

输入输出样例

输入 #1

Code2 行
3 
1 2 9

输出 #1

Code1 行
15

说明/提示

对于 的数据,保证有 :

对于 的数据,保证有 ;

对于全部的数据,保证有 。


题目深度剖析

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

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

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

假设第 堆初始果子在最终二叉树中所处的深度为 (定义根节点的深度为 ):

  • 深度 恰好代表了第 堆果子在整个合并历史中被累加计算的总次数。
  • 因此,合并所有果子所消耗的总精力,可以用经典的**带权路径长度(WPL, Weighted Path Length)**精确表示:

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

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

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

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

  1. 贪心选择性质(Greedy Choice Property):

    • 设当前集合中权值最小的两堆果子分别为 与 ,不妨设 。
    • 假设存在某个全局最优合并方案 ,其中 和 并不都在最深层作为兄弟节点合并。
    • 在最优二叉树 中,必然存在某对位于最深层的兄弟叶子节点 和 (其深度满足 )。
    • 根据定义,必然有 且 。
    • 若我们将在最深层的节点 与较浅层的节点 交换位置,树的带权路径长度变化量为:
    • 因为 且 ,所以 且 ,故 。
    • 交换后新的树消耗体力不会增加,甚至可能更小!
    • 同理,将 与 交换位置,带权路径长度同样不会增加。
    • 这充分证明:必然存在一个最优解,其中最小的两堆果子位于最深层并且互为兄弟节点首先合并。
  2. 最优子结构(Optimal Substructure):

    • 当我们把权值最小的两堆 合并为权值为 的新堆后,消耗体力为 ;
    • 剩余问题变为在包含新堆在内的 堆果子中继续求最小合并体力。根据二叉树子树递归性质,原问题的最优解严格依赖于合并后子问题的最优解。

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

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

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

  • 算法 1:朴素数组排序(初学者易错思路)

    • 每合并一次,重新调用 sort 排序,或者用插入排序将新元素插回有序数组。
    • 次合并,每次维护有序序列需 ,总时间复杂度为 。
    • 当 时, 次运算,在 1 秒时限内极度边缘甚至直接超时(TLE),无法作为满分标程。
  • 算法 2:STL 优先队列 / 小顶堆(推荐标准解法,GESP 五级 / CSP-J 核心)

    • 利用二叉小顶堆(std::priority_queue<long long, vector<long long>, greater<long long>>)动态维护集合。
    • 将 个数全部插入小顶堆,建堆时间复杂度为 。
    • 进行 轮合并:每轮执行两次 top() + pop() 取出最小两项,相加后通过 push() 放回堆中。每次堆调整仅需 。
    • 总时间复杂度严格为 ,总基本操作步数仅约 次,耗时在毫秒级以内,代码简练优美且极其稳健。
  • 算法 3:双单调队列优化(NOIP / CSP-S 进阶算法思维)

    • 观察生成的果子重量序列:如果我们将初始数组从小到大排序放入队列 ;
    • 每次合并得到的“新果堆”放入另一个队列 。
    • 数学性质保证:由于每次合并的都是当前全集中的最小值,后合并出的新堆重量必然不小于先合并出的新堆重量,因此队列 内部的元素天然单调递增!
    • 每一轮只需从 和 队头比较取最小值,单次操作 ,整体合并仅需 。结合初始排序后总时间复杂度依然受制于排序的 (若使用计数排序甚至可达到全流程 )。这一双单调队列思想正是后续信奥名题「NOIP 蚯蚓」的核心灵魂。

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

  1. 大顶堆与小顶堆的混淆:

    • C++ STL 的 priority_queue<long long> 默认是大顶堆(优先弹出最大值)。
    • 本题必须显式传入三个模板参数:priority_queue<long long, vector<long long>, greater<long long>> 才能正确初始化为小顶堆。
  2. 整型溢出防范:

    • 尽管洛谷题面给出了“输入数据保证这个值小于 ”的提示,但若在极限数据下(例如构造特定退化的偏斜树),累加过程很容易触及甚至溢出 32 位有符号整型上限(约 )。
    • 在竞赛与考级中,涉及累加代价的变量务必统一采用 long long 声明,坚决杜绝溢出风险。
  3. 的边界情况:

    • 若果子一开始就只有 堆,则完全不需要进行任何搬运合并,消耗体力为 。
    • 使用 while (pq.size() > 1) 作为循环条件,当 时循环体根本不会执行,直接输出初始值 total_cost = 0,逻辑自然闭环。

5. 复杂度深入分析

  • 时间复杂度:
    • 将 个数全部推入优先队列耗时 ;
    • 循环合并 次,每次执行 2 次堆弹出和 1 次堆插入,单次时间为 ( 为堆当前大小);
    • 总时间复杂度严格为 。代入 , 次计算,在 时限内仅需约 ,秒级通过。
  • 空间复杂度:
    • 优先队列中最多同时存放 个元素,额外空间复杂度为 ,占用内存小于 ,远低于题目限制。

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

C++55 行
/**
 * Problem: luogu-P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G
 * Algorithm: 贪心算法 (Greedy) / 优先队列 (Min-Heap / std::priority_queue) / 哈夫曼树 (Huffman Tree)
 * Standard: C++11 (CCF GESP 官方大纲规范)
 * Author: OneCoder
 */

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    int n;
    cin >> n;

    // 使用小顶堆(优先队列)维护当前所有果子堆的重量
    // greater<long long> 表示堆顶始终保持当前所有元素中的最小值
    priority_queue<long long, vector<long long>, greater<long long>> pq;

    // 读取 n 堆果子的初始重量并依次压入小顶堆中
    for (int i = 0; i < n; ++i) {
        long long x;
        cin >> x;
        pq.push(x);
    }

    // 记录合并果子总共消耗的最小体力
    long long total_cost = 0;

    // 每次合并必定选出当前最小的两堆果子(贪心策略 / 哈夫曼树构建过程)
    // 经过 n - 1 次合并后,优先队列中最终只剩下 1 堆果子
    while (pq.size() > 1) {
        // 取出当前重量最小的第一堆
        long long first = pq.top();
        pq.pop();

        // 取出当前重量最小的第二堆
        long long second = pq.top();
        pq.pop();

        // 两堆合并所消耗的体力等于两堆重量之和
        long long merged = first + second;
        total_cost += merged;

        // 将合并生成的新果子堆放回小顶堆中,参与后续的合并
        pq.push(merged);
    }

    // 输出最小总体力消耗值(若 n = 1,无需合并,输出 0)
    cout << total_cost << endl;

    return 0;
}
看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!