【NOI2015】荷马史诗

链接：http://uoj.ac/problem/130

 因为不能有前缀关系，所以单词均为叶子节点，就是K叉哈夫曼树。第一问直接求解，第二问即第二关键字为树的高度。

#include< cstdio >#include< algorithm >typedef unsigned long long ull;templateinline void read(T&x){	x=0;bool f=0;char c=getchar();	while((c<‘0‘||c>‘9‘)&&c!=‘-‘)c=getchar(); if(c==‘-‘)f=1,c=getchar();	while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}	x=f?-x:x;}const int MAXN(100010);struct Data{	ull val;int dep;inline bool operator <(const Data &A)const {return (val==A.val)?dep>A.dep:val>A.val;}}h[MAXN],New;int top;int n,k,First;ull Ans,sum,w[MAXN];void umax(int &a,int b){if(a<b)a=b;}int main(){//	freopen("C.in","r",stdin);//	freopen("C.out","w",stdout);	read(n);read(k);	for(int i=1;i<=n;i++)read(w[i]),sum+=w[i];	for(int i=1;i<=n;i++)h[++top]=(Data){w[i],1};	std::make_heap(h+1,h+1+top);	First=(n-1)%(k-1) +1;//	printf("%d\n",First);//	printf("%llu\n",sum);	if(First>1||n==1)	{	for(int i=1;i<=First;i++)	{		New.val+=h[1].val;		Ans+=h[1].val;		umax(New.dep,h[1].dep);		std::pop_heap(h+1,h+1+top);top--;			}	New.dep++;h[++top]=New;	std::push_heap(h+1,h+1+top);	}	while(top>1)	{		New.val=New.dep=0;		for(int i=1;top&&i<=k;i++)		{			New.val+=h[1].val;			Ans+=h[1].val;			umax(New.dep,h[1].dep);			std::pop_heap(h+1,h+1+top);top--;		}		New.dep++;//		printf("%llu %d\n",New.val,New.dep);		h[++top]=New;		std::push_heap(h+1,h+1+top);	}	printf("%llu\n",Ans);	printf("%d\n",h[1].dep-1);	return 0;}

UOJ#130 【NOI2015】荷马史诗 K叉哈夫曼树