[NOI2015]荷马史诗

上一篇文章《重编码-Huffman树WPL问题》解释了二叉Huffman树WPL问题,而这道题将二叉拓展到了K叉。

K叉与二叉的区别主要在一下几个地方

  • 节点数可能不足以满足K叉Huffman树的结构,需要补充虚拟节点
  • 在弹出节点时不是弹出2个,而是K个。

再就是本体还需要输出最长字符串的最短长度,也就是Huffman编码的最长长度。这里我们用一个pair来维护该节点在Huffman树的深度,也就是所求值。

先给出参考代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long,long long>;

int n,k;
priority_queue<pll,vector<pll>,greater<pll> > q;
ll ans;

int main() {
    ios::sync_with_stdio(false);

    cin >> n >> k;

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

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

    while(q.size() >= (unsigned long int) k) {
        ll depth = -1;
        ll sum = 0;
        for(int i = 1; i <= k ; ++i) {
            sum += q.top().first;
            depth = max(depth,q.top().second);
            q.pop();
        }

        q.push({sum,depth + 1});
        ans += sum;
    }

    cout << ans << endl << q.top().second << endl;

    return 0;
}

这里解释几个个关键性的问题:

  • 为什么要使节点数满足(q.size() - 1) % (k - 1) = 0?

为了防止在最后有节点剩余而无法合并,此时的局面不为最优解(此时答案偏小)。这个时候添加词频为0的虚拟节点可以满足K叉Huffman树的结构且不会影响到答案(相当于把节点“挤”到更优位置)。

  • 如何证明这个算法是对的?

其实和二叉Huffman树的道理是一样的,只不过我们在这里拓展成了K叉而已,如果还是无法理解算法过程可以手动模拟一遍。

(我懒,就不放模拟过程的图了)

  • 节点的深度是如何维护的?

道理很简单,对于一个节点,我们弹出来求了一次和(sum),就相当于把这层深度上的K叉Huffman树节点“砍掉了”。这个时候我们只需要找出这之中最大深度加上1,就可以维护节点最大深度了。

Last modification:April 21st, 2019 at 03:43 pm
博客维护不易,如果你觉得我的文章有用,请随意赞赏

Leave a Comment