合并果子题解

核心技巧：优先队列，堆，贪心，树；

题目内容；我们要将所有的果子堆都合并在一起且每次只能合并两堆，又因为每一次合并的消耗是两堆果子的重量之和，所以我们每次和并都应选择当前情况下的重量最小的两堆，直到只剩下一堆果子；
众所周知stl中有优先队列可以直接用，但是为了锻炼自己我还是选择了手写了优先队列的相关函数，也能帮助我更好的理解优先队列。
萌新一只，有错请指出；
代码如下；

#include<iostream>
using namespace std;
int p[100010],tot;//tot是用来计数的；
void push(int x){
    tot++;
    p[tot]=x;
    int i=tot;
    int j=i/2;
while(j>0&&p[j]>p[i]&&p[j]!=0){
        swap(p[i],p[j]);
        i=j;
        j=i/2;
    }

}
int pop_front(){
    return p[1];//这个其实可以不用写，只需要知道第一个是最大的直接使用就是；
}
void pop(void){
    p[1]=p[tot];
    tot--;
    int i=1;
    int j=2*i;
    if(p[j]>p[j+1]&&j+1<=tot)j+=1;//子节点中肯定优先选择与小的那个交换，所以需要比较左右子节点的大小；
    while(j<=tot&&p[j]<p[i]){
        swap(p[j],p[i]);
        i=j;
        j=i*2;
        if(p[j]>p[j+1]&&j<=tot-1)j+=1;//同上；
    }
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int b;
        cin>>b;
        push(b);
    }
    int ans=0;
    for(int i=1;tot>1;i++){
        int x=pop_front();
        pop();
        int y=pop_front();
        pop();
        ans+=x+y;
        push(x+y); 
    }
    cout<<ans<<endl;
    return 0;
}