题意分析

  • 给你一个序列，需要将这个序列进行两两合并，最后合并成一个数字。每次合并的花费就是这两个数字的和乘上一个c，问合并成一个数字的最小的花费是多少？

思路分析

  • 学过数据结构的同学应该都知道，这一题是一个很经典的类似于哈夫曼树的题目。解题的方法就是每次找到当前最小的两个数字，然后将这两个数字合并成一个数字放到原来的集合里面。每次累加花费即可。所以其实就是要我们构造出一棵哈夫曼树，在每次合并子节点的过程中累加我们得到的结果即可。

图片说明

解法一 优先队列（小根堆）

  • 在C++里面有一个很好用的STL容器，就是小根堆了，它为我们封装好了堆的一些基本的操作。每次都会自动调整这个堆，使得最小值在堆顶，我们可以直接O(1)取堆顶的数字即可。

  • 代码如下

    • 需要遍历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
        // 定义一个小根堆
        priority_queue<long long,vector<long long>,greater<long long> > q;
        for(auto x:a){
            q.push(x);
        }
        long long ans=0;
        while(1){
            // 如果此时堆中的元素的个数小于2，那么得到了最后的结果
            if(q.size()==1) break;
            // 取出堆顶的两个最小的数字
            long long tmp1=q.top();
            q.pop();
            long long tmp2=q.top();
            q.pop();
            // 组合成一个新的数字
            ans+=c*(tmp1+tmp2);
            // 新组成的数字入堆
            q.push(tmp1+tmp2);
        }
        return ans;
    }
};

解法二 （map红黑树）

  • 我们平时经常用map来进行离散化，但是可能很少有人注意到我们map内部其实是可以进行排序的，它的内部是红黑树实现。按照键的大小进行排序的。所以我们可以利用这个性质解决本题。我们先将数字都存入map里面。然后我们可以每次取出map指针第一个位置的元素，取出这个元素。如果这个元素取完了，那么在map里面删除这个元素即可。
  • 代码如下
    • 每次map里面的元素变动都会导致map进行重新调整，时间复杂度为
    • 利用map存储元素的值，空间复杂度为 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 表示有n个数。
     * @param c int整型 参数c
     * @param a int整型vector ai表示第i个数的大小
     * @return long长整型
     */
    typedef long long ll;
    ll get(map<ll,ll> &mp){
        auto x=*mp.begin();
        int y=x.first;
        mp[y]--;  //取出一个
        if(mp[y]==0){ // 如果此时的数字取完了，那么删除这个数字
            mp.erase(mp.find(y));
        }
        return y;
    }
    long long solve(int n, int c, vector<int>& a) {
        // write code here
        map<ll,ll> mp;
        for(auto x:a){
            mp[x]++;
        }
        int cnt=0; // 记录消除了多少个数字
        ll ans=0;
        while(cnt<n-1){
            int x=get(mp); // 获得map里面的键最小的数字
            int y=get(mp);  // 获得map里面的键最小的数字
            ans+=c*(x+y);
            mp[(x+y)]++;
            cnt++;
        }
        return ans;
    }
};