题目概述

有 $n$ 个单词，要给每个单词对应一个 $k$ 进制数，使得所有单词变为 $k$ 进制数之后接起来长度最小，并且满足在长度最小的前提下最长 $k$ 进制数最短，且 $k$ 进制之间不能有前缀关系。

解题报告

一看就是哈夫曼编码？但是前缀关系是什么鬼？其实把哈夫曼树建出来之后就是个Trie，所有单词都是叶子节点，显然没有前缀关系……

那么就是做 $k$ 叉哈夫曼树，如果 $n$ 个单词不足够让所有节点都 $k$ 叉怎么办？正确姿势是补零而不是最后做不满 $k$ 叉。至于最长的数最短只需要改变下优先级。

示例程序

#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=100000;

int n,K,si;pair<LL,int> Heap[maxn+5];LL ans;int MAX;

#define Push(x) (Heap[++si]=(x),push_heap(Heap+1,Heap+1+si))
#define Pop() (pop_heap(Heap+1,Heap+1+si--))
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&K);for (int i=1;i<=n;i++) {LL x;scanf("%lld",&x);Push(mp(-x,0));}
    if ((n-1)%(K-1)) for (int i=1,t=K-1-(n-1)%(K-1);i<=t;i++) Push(mp(0,0));
    while (si>1){
        LL A=0;int B=0;for (int t=1;t<=K;t++) A-=Heap[1].fr,B=max(B,-Heap[1].sc),Pop();
        B++;ans+=A;MAX=max(MAX,B);Push(mp(-A,-B));
    }printf("%lld\n%d\n",ans,MAX);return 0;
}