P2168 [NOI2015]荷马史诗

创建一个哈夫曼树，不同的是一个节点可以有 $k$ 个子节点，并且根节点没有任何编码。

考虑我们构造编码的过程，每次可以选择 $k$ 个子树，将它们合并为一个大的树，并且给子树们的根节点编号钦定为 $0,1,...k-1$ ，此时每个子树深度增加 $1$ ，这棵树的深度变为 $\max(maxdep(subtree_i))+1$ ，对答案的贡献为 $\sum sz(subtree_i)$ 。

于是我们可以用一个优先队列，贪心地取出 $sz$ 前 $k$ 大的树，然后合并，最后插入优先队列中。

注意到有不能取完的情况，我们需要在第一次操作取出恰当数目的树，使得后面能够刚好合并完。

#include <bits/stdc++.h>
#define MAXN 100005
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
int a[MAXN];
struct node{
	long long val,dep;
};
inline bool operator < (const node &A,const node &B){
	if (A.val!=B.val) return A.val>B.val;
	else return A.dep>B.dep;
}
#undef int
int main(){
#define int long long
	int n=read(),k=read();
	for (register int i=1;i<=n;++i){
		a[i]=read();
	}
	priority_queue<node>Q;
	for (register int i=1;i<=n;++i){
		Q.push(node{a[i],0});
	}
	long long ret=0;
	int fri=0;
	int tempn=n;
	while (true){
		if (tempn>=k){tempn-=k,tempn++;}
		else{fri=tempn;break;}
		if (tempn==1){fri=k;break;}
	}
	while (true){
		int max_dep=0,sz=Q.size();
		long long sum=0;
		int bound=0;
		if (fri) bound=fri,fri=0;
		else bound=k;
		for (register int i=1;i<=bound;++i){
			node t=Q.top();Q.pop();
			max_dep=max(max_dep,t.dep);
			sum+=t.val;
		}
		ret+=sum;
		Q.push(node{sum,max_dep+1});
		if (Q.size()==1) break;
	}
	node ans=Q.top();
	printf("%lld\n%lld\n",ret,ans.dep);
}