题解 | #牛牛算数#

题目：牛牛现在在学习计算机，他想通过计算机计算n个数的和。
但是计算机计算数字的和是有花费的，比如计算x，y两个数的和，需要花费 $(c*x+c*y)$ 秒。
计算机一次只能计算一次，牛牛想知道自己怎么合理安排计算的顺序，可以使得花费的时间最短。
输出计算n个数字和的最小花费的时间。
方法一：调用优先级队列函数
计算两个数所用时间为 $(c*(x+y))$ 秒，则计算n个数花费时间为 $图片说明$ ,因此我们可以使用优先级队列函数，每次让队头最小的两个元素先出队，计算累加时间，让两个出队元素相加后的结果入队

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 表示有n个数。
     * @param c int整型 参数c
     * @param a int整型一维数组 ai表示第i个数的大小
     * @return long长整型
     */
    public long solve (int n, int c, int[] a) {
        // write code here
        PriorityQueue<Integer>heap=new PriorityQueue<>();//小根堆
        for(int i=0;i<a.length;i++){
            heap.offer(a[i]);//元素加入小根堆
        }
        long res=0;
        while(heap.size()>1){
            int num1=heap.poll();
            int num2=heap.poll();
            int temp=num1+num2;//相加后结果
            res+=temp*c;//累加计算时间
            heap.offer(temp);//相加结果入堆
        }
        return res;
    }
}

复杂度：
时间复杂度：优先级队列的元素不超过n，每次出队最小元素的时间复杂度为 $图片说明$ ,因此时间复杂度为 $图片说明$
空间复杂度：队列元素不超过n， $O(n)$
方法二：建堆
不调用库函数我们也可以直接建一个最小堆，这里构造一个插入函数和一个删除函数，
插入函数中每次将要插入的元素放在堆底，不断向上调整，如果要插入的元素值小于符结点值，则父结点和插入元素的值交换，更新父结点和还是结点的值，如果要插入的元素值已经大于父结点的值，说明已经是个最小堆，不用调整
删除函数中将堆底元素和堆顶元素交换，除堆底元素外其他元素进行调整成最小堆

图片说明

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 表示有n个数。
     * @param c int整型 参数c
     * @param a int整型vector ai表示第i个数的大小
     * @return long长整型
     */

    long long solve(int n, int c, vector<int>& a) {
        // write code here
        vector<int>heap(n);
        int cnt=0;
        for(int i=0;i<n;i++){
            offer(heap,cnt++,a[i]);
        }
        long res=0;
        while(cnt>1){
            int num1=poll(heap,cnt--);
            int num2=poll(heap,cnt--);
            int temp=num1+num2;
            res+=c*temp;
            offer(heap,cnt++,temp);
        }
        return res;
    }
     int poll(vector<int>&heap,int n){
         int temp=heap[0];//保存堆顶元素
         heap[0]=heap[n-1];//堆底元素赋值给堆顶元素
         int parent=0,left=1,right=2;
         //调整堆为最小堆
         while(left<n){
             int k=left;
             if(right<n&&heap[right]<heap[left])k++;//右孩子比左孩子小，选右孩子
             if(heap[k]>heap[parent])break;//如果左孩子已经大于父亲，已经是最小堆则不用调整
             else{
                 int temp=heap[k];//否则，交换父亲和孩子
                 heap[k]=heap[parent];
                 heap[parent]=temp;
                 parent=k;//更新父亲和左右孩子
                 left=parent*2+1;
                 right=parent*2+2;
             }
         }
         return temp;
    }
    void offer(vector<int>&heap,int n,int k){
        heap[n]=k;//将要插入的元素放在堆最后面
        if(n==0)return;
        int child=n;
        int parent=(child-1)/2;//父结点
        while(parent>=0){
            if(heap[child]>=heap[parent])break;//要插入的孩子结点值已经大于父结点，直接跳出循环
            int temp=heap[child];
            heap[child]=heap[parent];
            heap[parent]=temp;//父结点和孩子结点交换
            child=parent;//更新孩子结点和父结点
            parent=(child-1)/2;
        }

    }
};

复杂度：
时间复杂度： $图片说明$ ，将n个元素插入堆，堆本质上是完全二叉树，因此插入函数的时间复杂度为 $图片说明$
空间复杂度: $O(n)$ ,堆的大小不超过n