[NOI2015]荷马史诗

Posted on | In

$K$维哈夫曼树模板题

从小往大贪心即可

最底层记得补零

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
#define pa pair < long long , int >
priority_queue < pa , vector < pa > , greater < pa > > Q ;
inline long long read () {
	char ch=getchar(); register long long num=0;
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) num=(num<<3)+(num<<1)+(ch^'0'),ch=getchar();
	return num;
}
int main () {
	register int n,k; scanf("%d%d",&n,&k); register long long ans=0;
	for(register int i=1;i<=n;++i) Q.push(make_pair(read(),0));
	while((n-1)%(k-1)!=0) ++n,Q.push(make_pair(0,0));
	while(Q.size()>=k) {
		pa u=make_pair(0,0);
		for(register int i=1;i<=k;++i) {
			pa v=Q.top(); Q.pop(); u.first+=v.first;
			u.second=max(u.second,v.second+1);
		}
		ans+=u.first; Q.push(u);
	}
	printf("%lld\n%d\n",ans,Q.top().second);
	return 0;
}