【BZOJ4198】荷马史诗

    多叉哈夫曼，同二叉哈夫曼，补几个权值为0的点即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long LL;

struct Node
{
	LL v,sum,dep;
	Node(LL _v=0,LL _dep=0,LL _sum=0):v(_v),dep(_dep),sum(_sum){}
	bool operator< (const Node &b) const {return v>b.v || v==b.v && dep>b.dep;}
};

priority_queue <Node> Q;

int n,k;

int main()
{
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++) {LL x;scanf("%lld",&x);Q.push(Node(x,1,0));}
	if (k>2) while (n%(k-1)!=1) Q.push(Node(0,1,0)),n++;
	while (n>1)
	{
		LL nv=0,nsum=0,ndep=0;
		for (int i=1;i<=k;i++)
		{
			Node x=Q.top();Q.pop();
			nv+=x.v;
			nsum+=x.sum+x.v;
			ndep=max(ndep,x.dep);
		}
		Q.push(Node(nv,ndep+1,nsum));
		n-=(k-1);
	}
	printf("%lld\n%lld\n",Q.top().sum,Q.top().dep-1);
	return 0;
}