题解 | #牛牛算数#

一.题目描述
NC575牛牛算数
计算x，y两个数的和，需要花费秒，并且每次只能计算一次，怎么合理安排计算的顺序，可以使得花费的时间最短，输出计算n个数字和的最小花费的时间。

二.算法(优先队列)
利用STL中的priority_queue来解决问题，用priority_queue来模拟小根堆，开始对所有花费时间插入堆中。每次弹出两个堆中元素对两个元素的和进行累加，然后将结果再放入堆中排序，直至堆中只有一个元素。最后的返回值是两个元素的和的累加值乘以c。

下面是完整代码：

class Solution {
public:
    long long solve(int n, int c, vector<int>& a) {
        //利用priority_queue建立小根堆
        priority_queue<int,vector<int>,greater<int>>q;
        for(int i=0;i<n;i++){
            //将所有的时间都入堆
            q.push(a[i]);
        }
        long long int sum=0;//记录累加值
        while(q.size()!=1){
            int x=q.top();
            q.pop();
            int y=q.top();
            q.pop();
            //弹出堆头的两个元素
            q.push(x+y);
            //两个数的累加值进队
            sum+=(x+y);
        }
        return sum*c;
    }
};

时间复杂度：对于n个元素每一个元素插入堆的时间复杂度是，所以时间复杂度是
空间复杂度： 堆的元素不超过n
优缺点：思路简单，代码实现容易
三.算法(模拟)
首先利用map对所用元素进行标记，然后每次找出所有时间中最小的那个时间并删除，连续两次操作，然后记录两个最小值累加的和，然后对于两个最小值的累加和进行标记，一次进行直至map中只有一个元素，返回两个最小值的和的累加值乘以c，下面是完整代码：

class Solution {
public:
    map<int,int>mp;
    //找到最小值返回并且删除最小值
    long long findmin(){
        //map会对前一个元素进行排序
        long long int mi=mp.begin()->first;
        if(--mp[mi]==0){
            //对最小值进行删除
            mp.erase(mi);
        }
        return mi;
    }
    long long solve(int n, int c, vector<int>& a) {
        long long sum=0;
        for(int i=0;i<n; i++){
            mp[a[i]]++;//对所有的时间进行标记
        }
        for(int i = 0;i<n-1;i++){
            long long x=findmin();//找到返回最小值并删除
            long long y=findmin();//找到返回最小值并删除
            sum+=(x+y);//对两个数的和进行累加
            mp[x+y]++; //标记两个数的和
        }
        return sum*c;
    }
};

时间复杂度： 进行了n次遍历，每一次操作时间复杂度是
空间复杂度： 对n个元素进行了标记
优缺点：思路简单，代码实现也容易