P2168:「NOI2015」荷马史诗题解

Introducing to the Huffman Tree

在《算法竞赛进阶指南中》，李煜东是这样描述哈夫曼问题的：

构造一棵包含 n 个子节点的 k 叉树，其中第 i 个叶子节点带有权值\(w_j\)，要求最小化\(\sum w_i*l_i\)，其中\(l_i\)表示第 i 个叶子节点到根节点的距离。

具体的哈夫曼树讲解请看：https://www.jianshu.com/p/95fba425be44

The Solution to This Problem

我们可以直接使用 Huffman 树生成中的计数功能，也就是说，我们在解题时不会真正的去建树，我们只是会记录累积的文章长度和最长的单词。我们可以直接在代码中体现：

// P2168.cpp
// tag:Huffman
#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;
const int maxn = 100200;
ll n, k, weights[maxn];
struct node
{
    ll val, mergeTimes;
    bool operator<(const node &nd) const
    {
        return val > nd.val || (val == nd.val) && (mergeTimes > nd.mergeTimes);
    }
};
priority_queue<node> seq;
int main()
{
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &weights[i]), seq.push(node{weights[i], 0});
    ll numOfZero = (k - 1) - (n - 1) % (k - 1);
    numOfZero %= (k - 1);
    for (int i = 0; i < numOfZero; i++)
        seq.push(node{0, 0});
    ll ans = 0, maxans = 0, L = 1;
    for (L = 1; seq.size() != 1; L++)
    {
        int siz = seq.size();
        ll curt = 0, max_val = 0;
        for (int i = 0; i < k; i++)
            curt += seq.top().val, max_val = max(max_val, seq.top().mergeTimes + 1), seq.pop();
        ans += curt, seq.push(node{curt, max_val}), maxans = max(maxans, max_val);
    }
    printf("%lld\n%lld", ans, maxans);
    return 0;
}