P2168 [NOI2015] 荷马史诗

题意

给定一个字符串 \(s\) 和整数 \(k\)。

求：1. k 叉哈夫曼树的带权路径之和；2. 求合法的哈夫曼树中，最小的高度是多少。

思路

1. 按照普通二叉哈夫曼树对其进行编码，将其转化为 \(k\) 叉哈夫曼树。
2. 编码有可能出现合并到根节点的时候不足 \(k\) 个结点，这会造成结果不优，所以我们可以补入一些长度为 \(0\) 的字符串使得任何一层都是满的。
3. 通过观察发现每次删除 \(k\) 个结点又补回来 \(1\) 个结点，所以每次减少 \(k - 1\) 个结点，最后剩下一个，所以我们可以一直补长度为 \(0\) 的字符串直到 \(n \equiv 1 (\bmod (k - 1))\)。

代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
using PII = pair<i64, int>;

const int N = 100010;

int n, k;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    priority_queue<PII, vector<PII>, greater<PII> > q;
    for (int i = 1; i <= n; i++) {
        i64 x;
        cin >> x;
        q.push({x, 0});
    }

    if (k > 2) {
        while (n % (k - 1) != 1) {
            n++;
            q.push({0, 0});
        }
    }

    i64 ans = 0;
    while (q.size() > 1) {
        i64 sum = 0;
        int max_dep = 0;
        for (int i = 1; i <= k; i++) {
            i64 x = q.top().first;
            max_dep = max(max_dep, q.top().second);
            q.pop();
            sum += x;
        }
        q.push({sum, max_dep + 1});
        ans += sum;
    }
    cout << ans << '\n' << q.top().second << '\n';
    return 0;
}