「BZOJ4198」[NOI2015]荷马史诗

Description

追逐影子的人,自己就是影子 ——荷马

Allison 最近迷上了文学。她喜欢在一个慵懒的午后,细细地品上一杯卡布奇诺,静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》 组成的鸿篇巨制《荷马史诗》实在是太长了,Allison 想通过一种编码方式使得它变得短一些。
一部《荷马史诗》中有n种不同的单词,从11nn进行编号。其中第ii种单 词出现的总次数为wiw_i。Allison 想要用kk进制串sis_i来替换第i种单词,使得其满足如下要求:
对于任意的 1i,jn,ij1 \leq i, j \leq n , i \neq j ,都有:sis_i不是sjs_j的前缀。
现在 Allison 想要知道,如何选择sis_i,才能使替换以后得到的新的《荷马史诗》长度最小。在确保总长度最小的情况下,Allison 还想知道最长的sis_i的最短长度是多少?
一个字符串被称为k进制字符串,当且仅当它的每个字符是 00k1k − 1 之间(包括 00k1k − 1 )的整数。
字符串 str1str_1 被称为字符串 str2str_2 的前缀,当且仅当:存在 1tm1 \leq t \leq m ,使得str1=str2[1t]str1 = str2[1\cdots t]。其中,mm是字符串str2str_2的长度,str2[1t]str_2[1\cdots t] 表示str2str_2的前tt个字符组成的字符串。

Input

输入的第 11 行包含 22 个正整数 n,kn, k ,中间用单个空格隔开,表示共有nn种单词,需要使用kk进制字符串进行替换。
接下来nn行,第 i+1i + 1 行包含 11 个非负整数wiw_i ,表示第 ii 种单词的出现次数。

Output

输出包括 22 行。
11 行输出 11 个整数,为《荷马史诗》经过重新编码以后的最短长度。
22 行输出 11 个整数,为保证最短总长度的情况下,最长字符串 sis_i 的最短长度。

Sample Input

1
2
3
4
5
4 2
1
1
2
2

Sample Output

1
2
12
2

HINT

对于所有数据,保证 2n100000,2k92\leq n\leq 100000,2\leq k\leq 9

Solution

二叉Huffman树构造方法:
不断从所有元素中找出最小值和次小值,把他们合并到一个新的结点上,新的结点权值为两个元素的权值之和,并且删除原来结点,直到元素个数只有11个为止。

题意是KK叉Huffman树,因为每一次合并会减少k1k-1个元素,最后要剩余一个,那么就是n(k1)t=1n-(k-1)t=1,也就是n1=(k1)tn-1=(k-1)t,因为为了保证合并次数为整数,那么(k1)(n1)(k-1)|(n-1)

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
41
42
43
44
45
46
47
48
49
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<ll,ll>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 110000;
ll n, m;
priority_queue<pii,vector<pii>,greater<pii> >q;

int main() {
ll ans1 = 0, ans2=0;
n = read(), m = read();
for(int i = 1; i <= n; ++i) {
ll x = read();
q.push(mk(x, 1));
}
while((n - 1) % (m - 1)) q.push(mk(0, 1)),++n;
while(q.size()>m) {
pii now;
for(int i = 1; i <= m; ++i) {
pii tmp = q.top(); q.pop();
now.fi += tmp.fi;
now.nd = max(now.nd, tmp.nd);
}
++now.nd;
ans1 += now.fi;
ans2 = max(ans2, now.nd);
q.push(now);
}
while(!q.empty()) ans1 += q.top().fi, q.pop();
writeln(ans1);
writeln(ans2);
return 0;
}