[P2168 NOI2015] 荷马史诗 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

重点：

1.k叉哈夫曼树如果子结点个数不满足(k-1)|(q.size()-1)，则补充空节点。

2.哈夫曼树的层数是根节点最大，所以把出现次数少的放在前面，而且出现次数相同把层数小的放前面，因为要先把层数小的合并成一个节点才能进行下一步操作。

题意：

n个单词，每个单词出现次数一定，用k进制给给每个单词搞编号，不能冲突。

分析：

建k叉的哈夫曼树。

代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

typedef long long ll;
ll n,k,ans;
struct node{
    ll w,h;
    node(){
        w=0;h=0;
    }
    node(ll w,ll h):w(w),h(h){}
    bool operator <(const node &b)const{
        return w==b.w?h>b.h:w>b.w;
    }
};
priority_queue<node>q;

inline ll read(){
    ll s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*w;
}

int main(){
    n=read();k=read();
    for(int i=1;i<=n;i++){
        ll x=read();
        q.push({x,1});
    }
    while((q.size()-1)%(k-1)!=0)q.push({0,1});
    //k-1是因为每个单词只能是叶子节点，并且每层有一个节点是下一层节点合并的，即每一层只有(k-1)个叶子节点
    //q.szie()-1是因为最下面一层有k个叶子节点
    while(q.size()>=k){
        ll h=0,w=0;
        for(int i=1;i<=k;i++){
            node tmp=q.top();
            q.pop();
            h=max(h,tmp.h);
            w+=tmp.w;
        }
        ans+=w;
        q.push({w,h+1});
    }
    cout<<ans<<endl<<q.top().h-1;
    return 0;
}