[NOI2015] 荷马史诗

题目链接

洛谷

LOJ

题目分析

哈夫曼编码模板题。 使用 $ k $ 进制，即编码时将 $ k $ 个点合并为一个。

最后要求的就是哈夫曼编码的长度，以及哈夫曼树最深的节点的深度。

注意最后合并的时候可能会出现不满一层的情况，所以要在刚开始补成能恰好合并的哈夫曼树。 最后剩下一个节点，即需要合并掉 $ n-1 $ 个点，而每次合并减少 $ k-1 $ 个点，所以要想恰好合并，需要满足

\[ (n-1) \bmod (k-1) = 0 \]

我们可以在合并之前就把权重为 0 的点加上凑数

代码实现

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100010;
typedef long long ll;
struct Node {
    ll w;
    ll depth;
    bool operator<(const Node& x) const
    {
        if (w != x.w) return w > x.w;
        return depth > x.depth;
    }
};

priority_queue<Node> q;
int n, k;
ll sum, ans, len;

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        ll ipt;
        cin >> ipt;
        q.push(Node{ipt, 0});
    }

    while ((q.size() - 1) % (k - 1) != 0) { 
        q.push(Node{0, 0});
    }

    while (q.size() > 1) {
        ll sum = 0, maxd = 0;
        for (int i = 1; i <= k; i++) {
            maxd = max(maxd, q.top().depth);
            sum += q.top().w;
            q.pop();
        }
        ans += sum;
        q.push(Node{sum, maxd + 1});
    }
    cout << ans << endl;
    cout << q.top().depth << endl;
    return 0;
}