「LOJ 2132」「NOI2015」荷马史诗

发表于

Allison 最近迷上了文学。她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了，Allison 想通过一种编码方式使得它变得短一些。

一部《荷马史诗》中有 nn 种不同的单词，从 11 到 nn 进行编号。其中第 ii 种单词出现的总次数为 wiw_i​​ 。Allison 想要用 kk 进制串 sis_i 来替换第 ii 种单词，使得其满足如下要求： 对于任意的 1≤i,j≤n, i≠j1 \leq i,j \leq n, \ i \neq j，都有：sis_i 不是 sjs_j 的前缀。

现在 Allison 想要知道，如何选择 sis_i ，才能使替换以后得到的新的《荷马史诗》长度最小。在确保总长度最小的情况下，Allison 还想知道最长的 sis_i 的最短长度是多少？

Constraints

2≤n≤1000002 \leq n \leq 100000 ， $ 2 \leq k \leq 9$ ， $ 0 \lt w_i \leq 10^{11}$

Solution

kk 维哈夫曼编码，将 kk 小的元素按规则合并即可。

哈夫曼编码具体右转 《霍夫曼编码（Huffman Coding）》 by xgf415

Code

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<algorithm> 
#include<cstring>
#include<queue>
#define LL long long
using namespace std;
const int N=1e5+5;
LL n,k,w,ans;
struct node
{
	LL w,h;
	bool operator < (const node& a) const {return w==a.w?h>a.h:w>a.w;}
}t,tp;
priority_queue<node> Q;
LL read()
{
	LL x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int main()
{
	n=read();k=read();
	for(int i=1;i<=n;i++)
		w=read(),Q.push((node){w,0});
	if(k>2)while(n%(k-1)!=1)n++,Q.push((node){0,0});
	for(int i=1;i<=n/(k-1)-(k==2);i++)
	{
		t.w=t.h=0;
		for(int j=1;j<=k;j++)
		{
			tp=Q.top();Q.pop();
			t.w+=tp.w;t.h=max(t.h,tp.h+1);
		}
		ans+=t.w;Q.push(t);
	}
	printf("%lld\n%lld",ans,Q.top().h);
	return 0;
}