「NOI 2015」 荷马史诗

题目地址

描述

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

Allison 最近迷上了文学。她喜欢在一个慵懒的午后,细细地品上一杯卡布奇诺,静静地阅读她爱不释手的《荷马史诗》。《荷马史诗》实在是太长了,Allison 想通过一种编码方式使得它变得短一些。

一部《荷马史诗》中有 $n$ 种不同的单词,从 $1$ 到 $n$ 进行编号。其中第 $i$ 种单词出现的总次数为 $w_{i}$。Allison 想要用 $k$ 进制串 $s_{i}$ 来替换第 $i$ 种单词,使得其满足如下要求:

  • 对于任意的 $1 \leq i,j \leq n$,$i \neq j$,都有:$s_{i}$ 不是 $s_{j}$ 的前缀。

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

分析

我们仔细分析一下发现好像和合并果子有一点像呀QAQ

$n$种不同的单词相当于树上的$n$个结点,我们可以把单词的出现次数$(w_{i}为第i个单词的出现次数)$当成该结点的权值,而结点到树的根结点的路径长度(也可以说是深度)就是$k$进制串$s_{i}$的长度$(l_{i}为第i个单词的长度)$,那么我们要最小化的就是

我们发现这和之前让我们最小化的哈夫曼树的$len$形式上是一样的,我们考虑哈夫曼树的构造过程其实就是“使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点”,那么这里也是一样的。

那么这其实就是最小化一棵$k$叉的哈夫曼树的带权路径长度。

刚开始我一直不明白为什么一定是一棵$k$叉哈夫曼树,其实很好理解,我们可以从哈夫曼编码的方面来思考:

  • 其实我们就是每次贪心使得出现次数最多的单词用$k$ 进制串 $s_{i}$ 替换后的 $s_{i}$ 长度最小
  • 而 $k$ 进制串 $s_{i}$ 的长度相当于结点到树的根结点的路径长度(也可以说是深度),那么我们要最小化深度
  • 也就是我们要尽量将哈夫曼树中每一层 $k$ 进制在当前层对应的 $k$ 个结点尽量填满
  • 那么也就是说一个满 $k$ 叉的哈夫曼树一定会更优一些

在 $k$ 叉哈夫曼树每回都满叉的情况下,我们像维护一棵普通的二叉哈夫曼树一样用一个优先队列来维护。

但是若存在哈夫曼树的某一层的上,哈夫曼树并不能满 $k$ 叉呢 QAQ
和我们构造最优二叉哈夫曼树一样每次合并引入虚拟结点令其权值为左右儿子权值之和,这里我们一样引入虚拟结点的概念,我们让权值为$0$的虚拟结点来填补使得 $k$ 叉哈夫曼树是满 $k$ 叉的。
我们每次更新 $n = n - k + 1$,然后判断 $(n - 1) \ \% \ (k - 1)$ 如果等于 $0$ 就是满 $k$ 叉;否则要用虚拟结点来填补,一共需要 $(k - 1) - ((n - 1) \ \% \ (k - 1))$ 个虚拟结点。

然而此题还要求 $s_{i}$ 的最大值最小,那么我们让$k$叉哈夫曼树的结点代表一个二元组 $(val,len)$,表示这个结点的权值和结点到根结点的路径长度。
在求最小 $k$ 个点时,把 $val$ 作为第一比较条件,如果 $val$ 值相等,则把 $len$ 小的放在前面,这样在每次合并的时候,长度小的点都会被优先合并,保证了根到叶子的最长链的长度尽量小。

所以,可以得到此题的算法:

  1. 用优先队列把 $(val,len = 0)$ push 进去,处理虚拟点 $(val = 0, len = 0)$。
  2. 每次用优先队列弹出前 $k$ 小的点,求它们的 $val$ 之和 $sum$,求它们的 $len$ 的最大值 $length$,那么将结点$(sum,length+1)$ 加入优先队列,且 $ans+=sum$。
  3. 当容器内只有一个点时,输出 $ans$ 和这个点的 $len$ 值。

最终时间复杂度是 $\Theta (nlogn)$。

代码

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
50
51
52
53
54
55
56
57
58
59
60
//  「NOI 2015」 荷马史诗
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
inline ll readIn() {
ll x = 0; int f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return (ll)x * f;
}
const int MAX_N = 100000 + 3;
const int INF = 0x3f3f3f3f;
ll n, k;
struct Node {
ll val, len;
Node (const ll val, const ll len) : val(val), len(len){}
bool operator < (const Node &rhs) const {
if (val == rhs.val) return len > rhs.len;//注意定义
return val > rhs.val;//
}
};
priority_queue<Node> q;
ll ans, sum, maxLen, cnt;

int main()
{
n = readIn(), k = readIn();
while (!q.empty()) q.pop();
for (int i = 1; i <= n; ++i) {
ll val = readIn();
q.push(Node(val, 0));
}

cnt = n;
if ((n - 1) % (k - 1)) cnt += ((k - 1) - ((n - 1) % (k - 1)));
for (int i = n + 1; i <= cnt; ++i) q.push(Node(0, 0));
/*
for (int i = 1; i <= n; ++i) {
Node cur = q.top(); q.pop();
printf("%lld %lld\n", cur.val, cur.len);
}
*/
ans = 0;
while (q.size() > 1) {
sum = 0, maxLen = 0;
for (int i = 1; i <= k; ++i) {
Node cur = q.top(); q.pop();
sum += cur.val;
maxLen = max(maxLen, cur.len);
}
ans += sum;
q.push(Node(sum, maxLen + 1));
}
printf("%lld\n%lld\n", ans, q.top().len);
return 0;
}
Partager