题解 | # 哈夫曼树 #

构造一棵含有 $n$ 个叶子节点的 $k$ 叉树，其中第 $i$ 个叶子节点带有权值 $w_{i}$ ，要求最小化 $\sum_{i=1}^{n}{w_{i}\times l_{i}}$ ，其中 $l_{i}$ 表示第 $i$ 个叶子节点的到根节点的距离。该问题被称为 $k$ 叉 $Huffman$ 树

题目一：https://www.luogu.com.cn/problem/P1090

这是经典的入门题，就是二叉哈夫曼树；最小化 $\sum_{i=1}^{n}{w_{i}\times l_{i}}$ ，那么贪心的想法是不断合并权值最小的两个 $w$ ，这样使得 $w$ 小的 $l$ 大， $w$ 大的 $l$ 小，用优先队列模拟。

因为有 $n-1$ 次合并操作，每次操作弹出与插入操作 $log$ 级别，所以时间复杂度为 $O(nlogn)$

题目二：https://www.luogu.com.cn/problem/P6033

题目一的加强版，必须使用 $O(n)$ 的时间复杂度解决二叉哈夫曼树

使用两个普通队列来操作，因为普通队列的操作时间复杂度为 $O(1)$ ；队列一存初始的所有权值 $a_{1},a_{2},...,a_{n}$ ，按照权值从小到大的顺序，队列二存合并之后的的权值

队列一怎么存储权值从小到大的 $a$ ：因为权值范围最大为 $10^{5}$ ，所以直接枚举 $1$ 到 $10^{5}$

int n; cin >> n;
vector<int> cnt(100000 + 10);
for(int i = 1; i <= n; i ++){
    int x; cin >> x;
    cnt[x] ++;
}

队列二存合并之后的的权值，队列二也是按照权值从小到大的顺序，因为依次合并的权值是从小到大的

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define debug(x) cout << #x << "= " << x << endl;
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


void solve(){

    int n; cin >> n;
    vector<int> cnt(100000 + 100);
    for(int i = 1; i <= n; i ++){
        int x; cin >> x;
        cnt[x] ++;
    }
    queue<int> q1, q2;
    for(int i = 1; i <= 100000; i ++){
       for(int j = 1; j <= cnt[i]; j ++) q1.push(i); 
    }
    int ans = 0;
    for(int i = 1; i <= n - 1; i ++){
        int sum = 0;
        for(int j = 1; j <= 2; j ++){
            if((!q2.size()) || (q1.size() && q1.front() < q2.front())) sum += q1.front(), q1.pop();
            else sum += q2.front(), q2.pop();
        }
        ans += sum;
        q2.push(sum);
    }
    cout << ans << endl;

    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

对于 $k$ 叉 $Huffman$ 树，似乎只需要仿照二叉哈夫曼树一样不断合并前 $k$ 个最小权值即可，然后如果在最后一次合并操作中，堆的大小在 $2$ 到之间（不足以取出 $k$ 个时），这显然不是最优解，因为只需要任意取已构建的 $Huffman$ 树的一个深度最大的节点修改为树根的子节点就会使 $\sum_{i=1}^{n}{w_{i}\times l_{i}}$ 更小。所以，在贪心之前，需要额外补充一些权值为 $0$ 的叶子节点使得叶子节 $k-1$ $n$ 满足 $(n-1)\ mod\ (k-1)\ =\ 0$ ，也就是说让子节点不足 $k$ 个的情况发生在最底层而不是根节点处。

题目三：https://www.luogu.com.cn/problem/P2168

回答两个问题：求最小的长度以及最小的深度

求最小长度，显然就是求 $k$ 叉 $Huffman$ 树
求最小深度，在求最小长度的基础上，贪心的优先选择深度小的值，此时合并的深度为 $max(depth_{1}, depth_{2},....,depth_{k})+1$

补充叶子节点

while((n - 1) % (k - 1)){
    q.push({0, 0});
    n ++;
}

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define debug(x) cout << #x << "= " << x << endl;
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


struct cmp{
    bool operator() (const pair<int, int> a, const pair<int, int> b) const{
        if(a.first != b.first) return a.first > b.first;
        else return a.second > b.second;
    }
};

void solve(){

    int n, k; cin >> n >> k;
    priority_queue<pair<int, int>, vector<pair<int, int> >, cmp> q;
    for(int i = 1; i <= n; i ++){
        int x; cin >> x;
        q.push({x, 0});
    }
    while((n - 1) % (k - 1)){
        q.push({0, 0});
        n ++;
    }
    int ans = 0;
    while(q.size() > 1){
        pair<int, int> res = {0, 0};
        for(int i = 1; i <= k; i ++){
            pair<int, int> now = q.top();
            q.pop();
            res.first += now.first;
            res.second = max(res.second, now.second);
        }
        ans += res.first;
        res.second ++;
        q.push(res);
    }
    cout << ans << endl << q.top().second << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}