3 条题解

  • 1
    @ 2026-10-24 10:43:03

    闲言

    这不是[模板]哈夫曼树吗,放在这是什么意思?

    我写个堆不就完了?

    不对,样例二挂了。

    kk 是什么??

    原来是 kk 叉的哈夫曼树。

    前文

    以防你不知道什么是哈夫曼树 &\And 哈夫曼编码,先来介绍一下。

    哈夫曼编码是一种压缩信息量的方法,著名的摩尔斯电码就是采用的这样的编码。

    哈夫曼编码的最大特点是编码的长度不等,如摩尔斯电码里的 EE 是一短(要么就是一长,反正他是最短的)。

    为什么要这么编码呢?

    可以发现 EE 是英语里面最常出现的字母,把他编的短一点应该可以很大降低电报长度,毕竟电报是按字数收钱的。

    又比如 Q,VQ,V 等,打几百个字母也就出现几次,编的长一点在整体上更优。

    但是我们遇到了一个问题:如何确保信息的准确传递呢?也就是说,怎么才能避免把长编码的一部分错认为短编码呢?

    要想保证正确性,必须保证每个编码不是某个编码的前缀。

    我们回到 OIOI 的方向,把每个串插入字典树,可以发现,每个叶子节点到根构成的字符串对应且仅对应一个编码,而非叶子节点不代表任何编码。

    我们设编码 ii 的出现概率为 PiP_i,长度为 LiL_i,则我们希望,编码的期望长度 EE 最小。

    由期望的线性性,可以知道 E=∑PiLiE = \sum P_i L_i。

    贪心地想,PiP_i 越小的编码长度应该越大,于是我们可以得出 0/10/1 哈夫曼编码的经典构造方法:初始时每个编码对应一个叶子节点,每次取概率最小的两个叶子,将其合并得到一个新叶子,新叶子的概率就是原概率之和。

    此处读者感性理解即可,证明详见 OI-wiki。

    好像一般翻译为霍夫曼树,但是我习惯叫哈夫曼,可能因为我当时这么学的吧。总之到网上搜要搜霍夫曼树。

    于是我们得到了经典的二进制哈夫曼算法,这样构造出来的树就是哈夫曼树。

    正文

    没错,写了这么多,我们终于要开始看这个题了。

    我们沿用二进制的算法来做,每次拿出最小的 kk 个点来合并,你会发现这样假了。

    原因很简单:如果最后一次合并没有凑齐 kk 个点,我们完全可以从最深的一层拿一个点上来安到根上,这样一定是更优的。

    简单归纳一下,可得:kk 进制哈夫曼算法最开始合并的一个点有小于等于 kk 个儿子,而其他所有非叶子节点都恰好有 kk 个儿子。

    于是我们把每种单词扔进堆里,按次数为第一关键字升序,高度为第二关键字升序,特判第一次合并,其他正常做就完事了。

    因为要保证长度和最小,所以这样一定能得到正确答案。

    细节上,第一次特判要选总点数取模 k−1k-1 的结果个点来合并,当 k=2k=2 时进入死循环,要特判一下。

    代码

    非常好写。

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    #define fi first
    #define se second
    int T,n,k;
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
    signed main(){
        ios::sync_with_stdio(0);
        cin.tie(0),cout.tie(0);
        cin>>n>>k;
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
            pq.push({x,0});
        }
        int ans=0;
        if(k==2){
            while(pq.size()>1){
                int s=pq.top().fi,d=pq.top().se;
                pq.pop();
                s+=pq.top().fi,d=max(d,pq.top().se);
                pq.pop();
                ans+=s;
                pq.push({s,d+1});
            }
            cout<<ans<<'\n'<<pq.top().se<<'\n';
            return 0;
        }
        while(pq.size()>1){
            int c;
            if(pq.size()%(k-1)==1) c=k;
            else c=pq.size()%(k-1);
            if(c==0) c=k-1;
            int s=0,d=0;
            while(c--){
                s+=pq.top().fi,d=max(d,pq.top().se+1),pq.pop();
            }
            ans+=s;
            pq.push({s,d});
        }
        cout<<ans<<'\n'<<pq.top().se<<'\n';
        return 0;
    }
    

    信息

    ID
    939
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    123
    已通过
    11
    上传者