树与哈夫曼树的应用

d

荷马史诗!(https://www.luogu.com.cn/problem/P2168)

实际上给定二叉树的最大的度,也就是一个根可以分几个叉,然后和二叉哈夫曼树一样,求最短带权路径长度.然后还需要判定出来最小的层数.

需要注意的点是,

1 为了保证最靠近根的结点的度是满的,需要预处理结点,也就是这里的lim,需要进行取余操作,然后每次将优先队列中最小的一批数合并,再重新放进队列之中.

2 判断最高的树层数问题,这就需要再设置一个标记量,因为优先队列只是根据权值进行排序,并未对不同的高度的树进行区分,而实际上,为了保证最小的高度,每次需要最矮的一批进行合并,然后再更新高度,这需要用pair来运算.下面的是未判定高度的代码.因此可以得出虽然二叉树对应着一个最小的长度,但是实际上,最高的层数不一定相等.

3.思路都没有问题,最后死在了没开long long的上面

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// 存进一个数字的权值和层数
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
// 多叉哈夫曼树
signed main() {
    int n, k; // 总结点数和一个k叉
    // 每次应该选择最小的k个数字 合并 然后再加入进去
    // 用优先队列
    cin >> n >> k;
    pair<ll, int> t;

    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        q.push({x, 0});
    }
    ll sum = 0;
    // 如果 n-1 不能被 k-1 整除，需要添加虚拟节点
    while ((n - 1) % (k - 1) != 0) {
        q.push({0, 0});
        n++;
    }
    while (q.size() > 1) {
        ll tmp = 0;
        int mx = 0;
        for (int i = 0; i < k; i++) {
            t = q.top();
            q.pop();
            tmp += t.first;
            mx = max(mx, t.second); // 这是最高层数
        }
        sum += tmp;
        q.push({tmp, mx + 1}); // 加入新的结点
    }
    cout << sum << "\n" << q.top().second;
}