题解 | #牛牛算数#

思路：

题目的主要信息：

• 的花费是
• 问数组a中所有元素全部相加求和的花费

假如按照顺序相加我们所需的花费就是：

也即答案为乘上一个数，因此我们不用管，最后乘上它即可。要想让后方这些数字相加和最小，我们可以用哈夫曼树的思想，每次寻找最小的两个数字相加，然后将和放入这些未加数字中，再比较，再找出最小的两个数字相加，这样花费将是最小的，哈夫曼树的构建如下图：

方法一：优先队列（小顶堆）
具体做法：
利用priority_queue模拟小顶堆，入堆后顶部都是最小的元素，每次只要弹出两个堆中元素，然后将结果再加入堆中排序即可。

class Solution {
public:
    long long solve(int n, int c, vector<int>& a) {
        long long res = 0;
        priority_queue<int, vector<int>, greater<int> > pq; //大顶堆
        for(int i = 0; i < n; i++) //全部进行堆排序 O(nlogn)
            pq.push(a[i]);
        while(pq.size() != 1){ //每次取最小的两个相加，结果进入堆中
            int x = pq.top();
            pq.pop();
            int y = pq.top();
            pq.pop();
            res += x + y;
            pq.push(x + y);
        }
        return res * c;
    }
};

复杂度分析：

• 时间复杂度：，两个外部循环都是，循环中出堆为，入堆为
• 空间复杂度：，priority_queue最大空间为

方法二：有序哈希（红黑树）
具体做法：
有这种思想的还有有序哈希表，其中借助了红黑树的排序原理，使得哈希表头一直都是最小key值，于是我们可以用key值表示数组a的待加数及中间和，value表示该数出现的次数，一旦出现次数为0，就将其从哈希表中删除，每次还是能取到最小的两个数相加。

class Solution {
public:
    long long getMin(map<int, int>& mp){ //获取最小值
        long long res = mp.begin()->first;
        if(--mp[res] == 0)
            mp.erase(res);
        return res;
    }
    long long solve(int n, int c, vector<int>& a) {
        long long res = 0;
        map<int, int> mp; //key为需要相加的次数，value为其出现的次数，次数为0从哈希表中删除
        for(int i = 0; i < n; i++)
            mp[a[i]]++;
        for(int i = 1; i < n; i++){ //每次取两个最小值相加，只有n-1次
            long long temp1 = getMin(mp);
            long long temp2 = getMin(mp);
            res += temp1 + temp2;
            mp[temp1 + temp2]++; //新值入哈希表
        }
        return c * res;
    }
};

复杂度分析：

• 时间复杂度：，有序哈希入表还是，外循环次
• 空间复杂度：，哈希表最大长度