Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


「NOI2015」荷马史诗 - 哈夫曼树

n n 种不同的单词,从 1 1 n n 进行编号。其中第 i i 种单词出现的总次数为 Wi W_i 。要用 k k 进制串 Si S_i 来替换第 i i 种单词,满足对于任意的 1i,jn, ij 1 \leq i,j \leq n,\ i \neq j ,都有:Si S_i 不是 Sj S_j 的前缀。

  1. 替换以后得到的新的长度最小为多少;
  2. 在确保总长度最小的情况下,最长的 Si S_i 的最短长度是多少?

链接

BZOJ 4198
UOJ #130

题解

考虑当 k=2 k = 2 时,其最优化条件相当于哈夫曼树,即:将所有单词作为一棵树放在集合中,每次取出两个最小的合并起来,放回集合,直到集合中只剩下一个元素。

显然,k2 k \neq 2 时,将「两个最小的」换成「k k 个」即可。

考虑第二个条件,使最长的 Si S_i 最短。在哈夫曼树算法中 Si S_i 的长度体现在一个节点被合并的次数上,只需要将每一个节点被合并的次数作为第二关键字即可。

最后一个问题,如果每次取出 k k 个,加入 1 1 个,最后不够 k k 个怎么办。考虑到每次减少了 k1 k - 1 个,需要将 n1 n - 1 个减掉 —— 只需加入一些空节点(Wi=0 W_i = 0 )使 即可。

代码

#include <cstdio>
#include <queue>
#include <utility>

const int MAXN = 100000;
const int MAXK = 9;

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    std::priority_queue< std::pair<long long, int>, std::vector< std::pair<long long, int> >, std::greater< std::pair<long long, int> > > q;

    for (int i = 0; i < n; i++) {
        long long x;
        scanf("%lld", &x);
        q.push(std::make_pair(x, 0));
    }

    while ((q.size() - 1) % (k - 1) != 0) q.push(std::make_pair(0, 0));

    long long ans = 0;
    while (q.size() > 1) {
        std::pair<long long, int> newNode;
        for (int i = 0; i < k; i++) {
            std::pair<long long, int> p = q.top();
            q.pop();
            ans += p.first;
            newNode.first += p.first;
            newNode.second = std::max(newNode.second, p.second);
        }

        newNode.second++;

        q.push(newNode);
    }

    std::pair<long long, int> p = q.top();
    printf("%lld\n%d\n", ans, p.second);

    return 0;
}