当前位置：首页 > news >正文

从合并果子到修篱笆：用C++优先队列（priority_queue）搞定两道经典贪心题

news 2026/8/15 22:29:13

从合并果子到修篱笆：用C++优先队列搞定两道经典贪心题

在算法竞赛的入门阶段，很多题目看似不同，实则暗藏相同的解题模型。今天我们要探讨的两道经典题目——合并果子（洛谷P1090）和修篱笆（USACO06NOV Fence Repair G），就是这种"形异神同"的典型案例。它们都源自同一个核心思想：哈夫曼编码的最优合并策略。

1. 两道题目的惊人相似性

乍看之下，合并果子和修篱笆似乎是完全不同的场景：

合并果子：需要将多堆果子合并成一堆，每次合并消耗的体力等于两堆果子的重量之和
修篱笆：需要将长木板切割成指定长度的小木板，每次切割的代价等于当前木板的长度

但仔细分析它们的操作过程，会发现惊人的一致性：

每次操作都涉及两个元素的合并/分割
每次操作的代价都与当前处理的元素大小成正比
目标都是最小化总操作代价

这种相似性不是巧合，而是因为它们都遵循最优合并树的数学模型——这正是哈夫曼编码所解决的问题。

2. 哈夫曼树模型解析

哈夫曼树（最优二叉树）的核心思想是：让频率高的元素靠近根节点，频率低的远离根节点。在合并果子问题中：

每个果堆的重量相当于叶节点的频率
合并过程相当于构建内部节点
总消耗体力等于所有内部节点的权重和

用数学表达式表示最小代价：

总代价 = Σ(每个内部节点的权重)

这个模型同样适用于修篱笆问题，只是操作方向相反——从整体分割到部分，但代价计算方式完全相同。

3. C++优先队列的两种使用方式

C++ STL中的priority_queue是实现这类问题的利器。下面我们比较两种不同的使用方式：

3.1 默认大顶堆与自定义小顶堆

标准库默认实现的是大顶堆（最大元素优先），但我们的问题需要小顶堆。有两种解决方案：

使用greater比较器：

priority_queue<int, vector<int>, greater<int>> minHeap;

存储负值利用默认大顶堆：

priority_queue<int> maxHeap; // 插入时 maxHeap.push(-value); // 取出时 int top = -maxHeap.top();

性能对比：

方法	代码简洁性	执行效率	可读性
greater	★★★★★	★★★★	★★★★★
负值转换	★★★	★★★★	★★

3.2 完整AC代码实现

以下是合并果子问题的标准解法：

#include <iostream> #include <queue> using namespace std; int main() { int n, sum = 0; cin >> n; priority_queue<int, vector<int>, greater<int>> pq; for(int i = 0; i < n; i++) { int num; cin >> num; pq.push(num); } while(pq.size() > 1) { int a = pq.top(); pq.pop(); int b = pq.top(); pq.pop(); int cost = a + b; sum += cost; pq.push(cost); } cout << sum << endl; return 0; }

关键操作解析：

pq.push(num)- 初始化小顶堆
pq.top()+pq.pop()- 获取并移除最小两个元素
sum += cost- 累加当前合并代价
pq.push(cost)- 将合并结果重新放入堆中

4. 时间复杂度分析与优化

使用优先队列的标准实现，时间复杂度为O(n log n)。让我们深入分析：

4.1 操作复杂度分解

建堆：O(n)
每次提取最小元素：O(log n)
共需n-1次合并操作

总复杂度：O(n) + O(n log n) ≈ O(n log n)

4.2 可能的优化方向

对于大规模数据（n>1e5），可以考虑以下优化：

双队列法：
- 维护一个原始队列和一个合并结果队列
- 每次从两个队列头部取最小值
- 可将复杂度降至O(n)（当输入已排序时）
基数排序预处理：
- 如果数值范围有限（如ai≤2e4）
- 先用O(n)的基数排序预处理
- 然后使用双队列法

优化后的代码框架：

void optimizedSolution() { // 1. 基数排序预处理 vector<int> counts(20001, 0); // ...计数排序实现... // 2. 初始化两个队列 queue<int> original, merged; // ...填充已排序数据到original队列... // 3. 双队列处理 while(/* 元素总数>1 */) { int a = getMin(original, merged); int b = getMin(original, merged); int cost = a + b; total += cost; merged.push(cost); } }