荷马史诗

为了满足题目中每个编码都不能是另一个前缀，因此用哈夫曼树可以实现，k进制就是k叉的哈夫曼树，哈夫曼树的带权路径和就是编码长度，树高就是字符串长度。

用最小优先队列实现最优合并，核心思路是先补 0 使节点数满足 k 叉哈夫曼树的结构要求，再循环取出权值最小的 k 个节点合并，累加求权值和，记录合并后节点的高度，重复这个操作直到队列里面只有一个元素，最终输出总长度和树高。

#define ll long long
using namespace std;

// 节点结构：w为权值，h为高度
struct node
{
    ll w,h;
    node(){w=0,h=0;}
    node(ll w,ll h):w(w),h(h){}
    // 使优先队列为权值小优先，权值相同则高度大优先
    bool operator <(const node &a)const{return a.w==w?h>a.h:w>a.w;}
};

ll ans; 
priority_queue<node>q; 
int main()
{
   ll n,k;
    cin>>n>>k;
    // 初始节点入堆
    for(int i=0;i<n;i++){
        ll w;
        cin>>w;
        q.push(node(w,1));
    }
    // 补0
    while((q.size()-1)%(k-1)!=0)q.push(node(0,1));
    
    // 循环合并k个最小节点
    while(q.size()>=k){
        ll w=0,h=-1;
        for(int i=0;i<k;i++)
        {
            node t=q.top();
            q.pop();
            h=max(h,t.h); // 取子节点最大高度
            w+=t.w;       // 累加权值
        }
        ans+=w; // 总代价累加
        q.push(node(w,h+1)); // 合并后的新节点入堆
    }
    // 输出总代价 + 有效树高
    cout<<ans<<endl<<q.top().h-1;
    return 0;
}

时间复杂度： O(nlogn) 空间复杂度： O(n)