题解 P2168 【[NOI2015]荷马史诗】

**description** 现在有一棵有 $n$ 个叶子节点 $k$ 叉树，每个叶子节点有一个权值 $s_i$，该节点到根的距离为 $l_i$，现在要最小化 $\sum s_il_i$ **solution** 一个 $k$ 叉哈夫曼树的板子题 显然我们要把权值大的尽量往上面放，把权值小的尽量往下面放。 所以我们可以用一个堆来维护，每次取出堆顶的 $k$ 个元素，求出他们的和 $sum$，累加到 $ans$ 中，然后再向堆中推入一个权值为 $sum$ 的数，以此类推。 但是这样会有一个问题，我们最后取到不足 $k$ 个的时候，我们的根节点的度数可能会不足 $k$，这个时候显然不优，因为我们希望上半部分的数尽量是满的。 解决方法是初始的时候往里面补 $0$ 我们发现每次我们要把点的数量减少 $k-1$，一共要消掉 $n-1$ 个点，所以我们只需要补到 $n-1\bmod k-1=0$ 时即可 注意此题第二问要求最长的字符串尽量的短，所以我们应该记录每个点的深度，在权值相同的时候优先取出深度低的点。 ```cpp # include <bits/stdc++.h> using namespace std; # define Rep(i,a,b) for(register int i=a;i<=b;i++) # define _Rep(i,a,b) for(register int i=a;i>=b;i--) # define RepG(i,u) for(int i=head[u];~i;i=e[i].next) typedef long long ll; const int N=3e5+5; template<typename T> void read(T &x){ x=0;int f=1; char c=getchar(); for(;!isdigit(c);c=getchar())if(c=='-')f=-1; for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0'; x*=f; } int n,k; ll ans; struct misaka{ ll val; int dep; bool operator < (const misaka &cmp)const{ if(val!=cmp.val)return val>cmp.val; return dep>cmp.dep; } }; priority_queue<misaka> q; int main() { read(n),read(k); Rep(i,1,n){ ll x; read(x); q.push((misaka){x,0}); } int qwq=(k-1-(n-1)%(k-1))%(k-1); Rep(i,1,qwq)q.push((misaka){0,0}); while(q.size()>1){ ll val_new=0; int dep_new=0; Rep(i,1,k){ misaka u=q.top();q.pop(); val_new+=u.val; dep_new=max(dep_new,u.dep); } ans+=val_new; q.push((misaka){val_new,dep_new+1}); } printf("%lld\n%d\n",ans,q.top().dep); return 0; } ```