[NOI 2015] 荷马史诗

知识点

哈夫曼树、优先队列、多目标贪心

解题思路

把k进制前缀码看作k叉树。补若干权重0的虚叶，使叶数减1能被k-1整除。每次取权重最小的k棵子树合并，权重相同时优先取高度较小者，维护总合并权重与高度。

正确性说明

前缀码对应叶子不为祖先的k叉树，带权路径长度等于各次合并权重之和。可在某个最优树中把最轻的k棵子树放为同一最深父节点的孩子，合并后缩小问题，得到Huffman贪心。相同权重交换不改变总长度，优先合并较矮子树避免把已有最长链继续加深，使最优总长度下的最大码长最小；补零叶使满k叉合并可行且不增加真实词的带权代价。

易错点

不能只按权重比较而忽略高度；每轮恰合并k个；补叶数取模，已整除时不补；权重和代价用64位。

复杂度

O(n log n)时间，O(n)空间，k≤9。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,k;cin>>n>>k;using P=pair<long long,int>;priority_queue<P,vector<P>,greater<P>>q;for(int i=0;i<n;i++){long long w;cin>>w;q.push({w,0});}int add=(k-1-(n-1)%(k-1))%(k-1);while(add--)q.push({0,0});long long ans=0;while(q.size()>1){long long sum=0;int h=0;for(int i=0;i<k;i++){auto[w,d]=q.top();q.pop();sum+=w;h=max(h,d);}ans+=sum;q.push({sum,h+1});}cout<<ans<<'\n'<<q.top().second<<'\n';}