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

【NOI2015】荷马史诗

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

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

#include< cstdio >

#include< algorithm >

typedef unsigned long long ull;

template

inline 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;

}