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

从合并果子到修篱笆用C优先队列搞定两道经典贪心题在算法竞赛的入门阶段很多题目看似不同实则暗藏相同的解题模型。今天我们要探讨的两道经典题目——合并果子洛谷P1090和修篱笆USACO06NOV Fence Repair G就是这种形异神同的典型案例。它们都源自同一个核心思想哈夫曼编码的最优合并策略。1. 两道题目的惊人相似性乍看之下合并果子和修篱笆似乎是完全不同的场景合并果子需要将多堆果子合并成一堆每次合并消耗的体力等于两堆果子的重量之和修篱笆需要将长木板切割成指定长度的小木板每次切割的代价等于当前木板的长度但仔细分析它们的操作过程会发现惊人的一致性每次操作都涉及两个元素的合并/分割每次操作的代价都与当前处理的元素大小成正比目标都是最小化总操作代价这种相似性不是巧合而是因为它们都遵循最优合并树的数学模型——这正是哈夫曼编码所解决的问题。2. 哈夫曼树模型解析哈夫曼树最优二叉树的核心思想是让频率高的元素靠近根节点频率低的远离根节点。在合并果子问题中每个果堆的重量相当于叶节点的频率合并过程相当于构建内部节点总消耗体力等于所有内部节点的权重和用数学表达式表示最小代价总代价 Σ(每个内部节点的权重)这个模型同样适用于修篱笆问题只是操作方向相反——从整体分割到部分但代价计算方式完全相同。3. C优先队列的两种使用方式C STL中的priority_queue是实现这类问题的利器。下面我们比较两种不同的使用方式3.1 默认大顶堆与自定义小顶堆标准库默认实现的是大顶堆最大元素优先但我们的问题需要小顶堆。有两种解决方案使用greater比较器priority_queueint, vectorint, greaterint minHeap;存储负值利用默认大顶堆priority_queueint 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_queueint, vectorint, greaterint 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 可能的优化方向对于大规模数据n1e5可以考虑以下优化双队列法维护一个原始队列和一个合并结果队列每次从两个队列头部取最小值可将复杂度降至O(n)当输入已排序时基数排序预处理如果数值范围有限如ai≤2e4先用O(n)的基数排序预处理然后使用双队列法优化后的代码框架void optimizedSolution() { // 1. 基数排序预处理 vectorint counts(20001, 0); // ...计数排序实现... // 2. 初始化两个队列 queueint 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); } }5. 从具体问题到通用模型理解这类问题的通用解法后可以轻松应对多种变体5.1 常见变体类型多路合并每次合并k个元素而非2个解决方案使用k叉堆或调整提取策略带约束合并某些元素不能直接合并解决方案增加约束条件判断动态元素合并过程中新增元素解决方案实时更新优先队列5.2 通用解题框架对于任何符合最优合并模型的问题都可以套用以下步骤识别问题类型确认是否属于合并/分割代价最小化问题数据结构选择优先使用小顶堆priority_queue贪心策略实施每次操作当前最小的两个元素代价累计维护一个全局总和变量终止条件只剩一个元素时结束5.3 实际应用案例这类算法不仅存在于竞赛中现实世界也有很多应用文件压缩哈夫曼编码任务调度优化网络数据传输打包资源分配策略在最近的一次编程比赛中就出现了这样一道变体题有n个任务每个任务需要特定时间完成。每次可以同时进行两个任务所需时间为两者之和。如何安排顺序使总完成时间最小这本质上就是合并果子问题的翻版只是换了个应用场景。