[NOIP2004 提高组]合并果子（贪心，优先队列，小根堆一口气学会）

本文主要是介绍[NOIP2004 提高组]合并果子（贪心，优先队列，小根堆一口气学会），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述
题目链接洛谷P1090

题意

意思就是给你一堆数(比如1 2 3)
让你加到只剩一个数(1+2+3=6)
每次加的代价是加出来的数(1+2=3 ，代价是3 ； 3+3=6 ，代价是6 ； 6+3为总代价)
要求最小代价(引入一种思想：贪心)

贪心

贪心算法，其实根本不用讲，它的核心思路就是求出局部最优解，走一步算一步，每一步都选当前的最优解，根本不从整体上考虑，然后把所有局部解求出来合成整体解。
举个例子，小红邀请小明和小军到小红家玩，但是小红家比较小，只能容纳两人在这里插入图片描述
从图上可以看出，小军无论怎么走都要走2km，然而小明有两条路可以走，一条是1km，一条是3km，如果你是小明，你会怎么走呢，很明显，走1km这条路，就可以愉快地跟小红一起玩耍了。
这就是贪心，选择局部的最优解，然后凑成整体的最优解，如果还不能理解
在这里插入图片描述
那么这次你会作何选择呢，当然是一直往前，而不是弯着走，但是你思考的时候，其实有把它们分开看，也就是，小明和小红家之间有一个必经中转点，所以要到达小红家就得先到必经中转点，到达必经中转点的最优路径是1，而必经中转点到小红家的最优路径也是1，所以这么走最快
你会发现，最终的答案是由局部得来的，而且依赖于前面的选择(不理解可以想想在小明到必经中转点那条2km的路径上再加一个点，然后把这个新点到达必经中转点的路径删掉，这样就到不了小红家了，所以它依赖于前面的选择)，这就是贪心

回归题目

讲了这么多，贪心应该懂了吧，现在回归题目，怎么求最小代价呢，那就分成局部问题吧，局部问题就是合成两堆果子的最小代价对吧，而合成两堆果子的最小代价很显然求，就是把这一大堆果子里把最小的两堆果子合在一起吧？
那解法就昭然若揭了，我们把这堆果子放进一个数据结构里，然后对它从小到大排序，每次取出最小的两个出来，加起来，放到最后，然后再排序一次，让这个新合成的果子找到自己的位置，循环往复，直到只有一堆，合成的过程记录一下代价就好了。

但是每次都排序这样的时间复杂度很大，即使是STL里的sort，每次排序也要 O(nlogn) 的时间,那么有什么数据结构能很快地完成排序这个重要的任务呢

堆

堆是一种特殊的二叉树，它分为小根堆，大根堆
树之所以叫树呢，是因为它长这样
在这里插入图片描述
你也可以这么看它

第一个"爸爸"结点呢，就叫根结点，每个结点有几个儿子就叫几叉树，但是按照爸爸的数值比儿子小这种存储方式的树，叫小根堆，爸爸存的数值比儿子大这种存储方式的树，叫做大根堆
也就是说，在大根堆里，最大的数，是根节点，在小根堆里，最小的数是根节点
我们一般用数组来模拟树，比如 tree[100] tree[1]为根结点，tree[2]和tree[3]为1的子结点，也就是，一个结点的儿子在数组中的位置为i*2和i*2+1这样就不会有重复，而且能很快查询父亲或者儿子了

用小根堆的代码如下，注解很多，如果不要注解，可以往下翻

有注解版

#include<bits/stdc++.h>
#define op <		//将此处的<号改成>号即为大根堆 
using namespace std; 
int heap[1000086]/*堆*/, size/*堆的长度*/;
void swim(int n)
{//接下来这段要熟悉for循环的执行顺序//for （ 循环开始时执行且只执行一次 ; 1  ; 3 ） {  2  } for (int i=n ; i>1/*不是根节点就上浮*/&&heap[i] op heap[i / 2]/*跟父结点比较*/ ; i /= 2)swap(heap[i], heap[i / 2]);
}//将子节点与父节点进行比较，不断上浮 
int son(int n)//如果左儿子比右儿子小，返回左儿子，不然返回右儿子 
{//此处的处理有点巧妙，本来是要比较左儿子与右儿子的大小//但是因为n的左儿子是2*n,右儿子是2*n+1//所以用一个判断式来代表这个1存不存在//下面的2*n是左右儿子的公有部分 //如果你觉得这样很复杂，可以重新写一个思路一样的更简单的，但是更长的代码 return n