题解 | #分金条的最小花费#

#include<bits/stdc++.h>
using namespace std;
//建堆函数
//引用的目的是为了同步改变堆的大小
void heapInsert(long long heapArray[],long long data,long long &heapSize);
//调整堆的函数
void heapfi(long long heapArray[],long long &heapSize);
int main(){
    long long n;
    cin>>n;
    long long *arr=new long long[n];
   long long heapArray[n];
    long long heapSize=0;//限制堆的大小
    for(long long i=0;i<n;i++){
        cin>>arr[i];
        //将其放入小根堆中
        heapInsert(heapArray, arr[i], heapSize);
    }
    //哈夫曼算法为每次挑选两个最小的数合成成一个大数，最后只剩下一个数时结束
    //所以n个数一共要进行n-1次合成
    long long res=0;
    for(long long i=1;i<=n-1;i++){
        //每次找两个最小的值
        //可以用小根堆求
        //每次取出堆顶以后都要调整小根堆
        long long data1=heapArray[0];
        heapfi(heapArray, heapSize);//调整成新的堆
        long long data2=heapArray[0];
        heapfi(heapArray, heapSize);//继续调整
        res+=data1+data2;
        //然后将合成的值放入小根堆中
        heapInsert(heapArray, data1+data2, heapSize);
    }
    cout<<res<<endl;
    return 0;
}
//建堆函数
void heapInsert(long long heapArray[],long long data,long long &heapSize)
{
    heapArray[heapSize++]=data;//将这个数放入堆中，并且堆的有效范围加一
    //向上调整
    long long pos=heapSize-1;//当前新加入的位置
    while(heapArray[pos]<heapArray[(pos-1)/2]){//当前值如果比他的父亲节点更小
        //交换与父亲节点的值
        long long temp=heapArray[pos];
        heapArray[pos]=heapArray[(pos-1)/2];
        heapArray[(pos-1)/2]=temp;
        pos=(pos-1)/2;//向上调整
    }
}
//向下调整
void heapfi(long long heapArray[],long long &heapSize)
{
    //拿最后一个数和第一个数交换，然后向下调整
    heapArray[0]=heapArray[--heapSize];
    long long pos=0;
    while(2*pos+1<heapSize){//当左孩子不越界时
        long long min=2*pos+2>=heapSize||heapArray[2*pos+1]<heapArray[2*pos+2]?2*pos+1:2*pos+2;
        if(heapArray[min]<heapArray[pos]){
            long long temp=heapArray[pos];
            heapArray[pos]=heapArray[min];
            heapArray[min]=temp;
            pos=min;//向下调整
        }
        else{//说明左右孩子中最小的那一个都比父亲的值大
            //退出
            break;
        }
    }
}