《算法竞赛进阶指南》0x17 二叉堆

二叉堆基本概念

二叉堆 是一种支持插入、删除、查询最值的数据结构

二叉堆 是一颗满足 “堆性质” 的 完全二叉树，树上的每个节点带有一个权值

根据 完全二叉树 的性质，一般堆的存储都采用层次序列存储方式，直接用数组来保存二叉堆

对于下标为

i

的结点，如果存在则其左儿子下标为

2i

，右儿子下标为

2i 1

，父节点下标为

lfloor dfrac{i}{2} rfloor

堆有两个核心操作，一个是向上调整，即 up 操作；一个是向下调整，即 down 操作

这两个核心操作的目的是维护当前堆所有结点的 “堆性质”，以大根堆为例，代码如下：

代码语言：javascript复制

void up(int u)
{
    while (u / 2 && w[u / 2] > w[u])
    {
        swap(w[u], w[u / 2]);
        u /= 2;
    }
}
void down(int u)
{
    int t = u;
    if (u * 2 <= n && w[u * 2] >= w[u]) t = u * 2;
    if (u * 2   1 <= n && w[u * 2   1] >= w[u]) t = u * 2   1;
    if (t != u) swap(w[u], w[t]), down(t);
}

堆的其他操作都是基于这两个核心操作之上的，例如：

• 入堆操作
  • 将元素放在数组的最后一位，然后扩大一位数组长度，并对最后一个位置执行向上调整
• 出堆操作
  • 将第一位元素与最后一位元素交换，然后减少一位数组长度，并对第一个位置执行向下调整

建堆

建堆操作分为向下建堆操作和向上建堆操作两种，分别进行介绍

向上建堆操作

从根节点开始，按照 BFS 序即可

代码语言：javascript复制

for (int i = 1; i <= n; i    ) up(i);

时间复杂度计算：

O(log 1 log 2 cdots log n) = O(nlog n)

向下建堆操作

按照逆 BFS 序操作即可

另外观察易得：叶结点不需要进行向下调整操作，因此可以从

dfrac{n}{2}

开始，减少常数

代码语言：javascript复制

for (int i = n / 2; i; i -- ) down(i);

时间复杂度计算：

O(dfrac{n}{2} cdot 1 dfrac{n}{2^2} cdot 2 dfrac{n}{2^3} cdot 3 cdots ) = O(n)

（等比等差交错项数列求和）

左偏树等会在以后详细讲解

习题

超市

题目描述

超市里有

N

件商品，每件商品都有利润

p_i

和过期时间

d_i

，每天只能卖一件商品，过期商品不能再卖。

求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。

输入格式

输入包含多组测试用例。

每组测试用例，以输入整数

N

开始，接下来输入

N

对

p_i

和

d_i

，分别代表第

i

件商品的利润和过期时间。

在输入中，数据之间可以自由穿插任意个空格或空行，输入至文件结尾时终止输入，保证数据正确。

输出格式

对于每组产品，输出一个该组的最大收益值。

每个结果占一行。

数据范围

0≤N≤10000, 1≤p_i,d_i≤10000

最多有 14 组测试样例

输入样例：

代码语言：javascript复制

4  50 2  10 1   20 2   30 1

7  20 1   2 1   10 3  100 2   8 2
   5 20  50 10

输出样例：

代码语言：javascript复制

80
185

解析

贪心的思维，我们希望对于当前所有未过期的商品，在有限天数内尽可能选取利润较高的商品

然后递推到下一个日期，如果有新的高利润商品，能选则选，不能选就考虑将之前选择的价值最小商品扔掉

也就出现了一个 “后悔” 的操作

显然，对于每个阶段来说，该贪心方案一定是能选则选，在出现多种方案时，处于选满状态

此时，从贪心方案中放弃一件商品，去选另外一个之前未选的商品，都不会使方案变好

故该贪心方案是正确的

做法就很简单，先按照过期天数排序，这个是我们划分阶段的关键

然后维护一个小根堆，要求每个阶段，小根堆的元素数量都小于等于当前阶段的天数

如果新元素插入会使小根堆超出阶段数，则比较堆顶元素与新插入的元素，保留较大的即可

代码语言：javascript复制

for (int i = 1; i <= n; i    ) scanf("%d%d", &a[i].p, &a[i].d);
sort(a   1, a   n   1);
priority_queue<int, vector<int>, greater<int>> heap;
for (int i = 1; i <= n; i    )
{
    heap.push(a[i].p);
    if (heap.size() > a[i].d) heap.pop();
}
int res = 0;
while (heap.size())
{
    res  = heap.top();
    heap.pop();
}
printf("%dn", res);

序列

题目描述

给定

m

个序列，每个包含

n

个非负整数。

现在我们可以从每个序列中选择一个数字以形成具有

m

个整数的序列。

很明显，我们一共可以得到

n^m

个这种序列，然后我们可以计算每个序列中的数字之和，并得到

n^m

个值。

现在请你求出这些序列和之中最小的

n

个值。

输入格式

第一行输入一个整数

T

，代表输入中包含测试用例的数量。

接下来输入

T

组测试用例。

对于每组测试用例，第一行输入两个整数

m

和

n

。

接下在

m

行输入

m

个整数序列，数列中的整数均不超过

10000

。

输出格式

对于每组测试用例，均以递增顺序输出最小的

n

个序列和，数值之间用空格隔开。

每组输出占一行。

数据范围

0<m≤1000, 0<n≤2000

输入样例：

代码语言：javascript复制

1
2 3
1 2 3
2 2 3

输出样例：

代码语言：javascript复制

3 3 4

解析

二叉堆的经典题型之一，各大书籍课程在二叉堆这一章节都会塞的一道例题，非常经典

考虑划分子问题，“每次从每个序列中选一个数字，组成长度为

m

的序列问题”，等价于 “从最后一个序列中选一个数字，再对前

m-1

个序列，每个各选一个数，组成长度为

m - 1

的序列，最后让这

m-1

个元素和第一开始选的一个元素，组成长度为

m

的序列问题”

继续划分到最小情况，即为：“对于两个长度为

n

的序列，各选一个数，构成长度为

2

的序列问题”

通过该划分子问题方法，每次我们就可以仅合并两个序列，问题就简单多了

蓝书上的做法：

如何合并两个序列，以简单情况为例，合并序列

A, B

，先对

A, B

排序

最小元素毫无疑问是

A[1] B[1]

，则次小元素候选为:

A[2] B[1], A[1] B[2]

假设次小元素为

A[2] B[1]

，则第三小元素候选为：

A[2] B[2], A[1] B[2], A[3] B[1]

不失一般情况，选出第

k

小元素

A[i] B[j]

时，会有两个新元素加入候选，即

A[i 1] B[j], A[i] B[j 1]

下一轮选出最小元素，即是在所有候选元素中选出一个最小的即可，因此想到用堆来维护候选序列

值得注意的是，

A[i 1] B[j]

和

A[i] B[j 1]

都会产生候选项：

A[i 1] B[j 1]

由于

A[i 1] B[j] < A[i 1] B[j 1]

且

A[i] B[j 1] < A[i 1] B[j 1]

故产生顺序肯定是先前两者，再后者，所以谁产生

A[i 1] B[j 1]

不重要，重要的是只能产生一个

为避免重复，不妨规定：产生候选项

A[x] B[y]

的操作如果是通过

j 1

实现的，则之后只能移动

j

指针

于是

A[1] B[1]

到任意

A[i] B[j]

必然是先到

A[i] B[1]

再到

A[i] B[j]

从而保证答案路线产生的唯一性

时间复杂度为：

O(MN log N)

代码语言：javascript复制

struct Node
{
    int i, j;
    bool last;
    bool operator > (const Node &t) const
    {
        return a[i]   b[j] > a[t.i]   b[t.j];
    }
};
void merge_array()
{
    priority_queue<Node, vector<Node>, greater<Node>> heap;
    heap.push({1, 1, false});
    for (int i = 1; i <= n; i    )
    {
        Node t = heap.top();
        heap.pop();
        tmp[i] = a[t.i]   b[t.j];
        if (!t.last) heap.push({t.i   1, t.j, false});
        heap.push({t.i, t.j   1, true});
    }
    memcpy(a, tmp, sizeof tmp);
}
void solve()
{
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; i    ) scanf("%d", &a[i]);
    sort(a   1, a   n   1);
    while ( -- m)
    {
        for (int i = 1; i <= n; i    ) scanf("%d", &b[i]);
        sort(b   1, b   n   1);
        merge_array();
    }
    for (int i = 1; i <= n; i    ) printf("%d ", a[i]);
    puts("");
}

y总的做法：

y总用的是分组的思想，同样是在处理 "两个序列的选择" 问题，考虑对

A

数组进行分组，有：

[ begin{matrix} A_1 B_1 & A_2 B_1 & cdots & A_n B_1 \ A_1 B_2 & A_2 B_2 & cdots & A_n B_2 \ cdots & cdots & cdots & cdots \ A_1 B_n & A_2 B_n & cdots & A_n B_n \ end{matrix} ]

由于

A

数组已经从小到大排好序，因此选出这

n

组中最小的元素，就是对第一列元素选出最小即可

选完

A_1 B_1

以后，第一组的指针就向后移动，构成如下分组情况：

[ begin{matrix} text{(chosen)} & A_2 B_1 & cdots & A_n B_1 \ A_1 B_2 & A_2 B_2 & cdots & A_n B_2 \ cdots & cdots & cdots & cdots \ A_1 B_n & A_2 B_n & cdots & A_n B_n \ end{matrix} ]

同理处理

n

轮分组情况即可，这个分组思想非常的巧妙，个人认为比蓝书漂亮

代码语言：javascript复制

//其余部分和上面一样
void merge_array()
{
    priority_queue<Node, vector<Node>, greater<Node>> heap;
    for (int i = 1; i <= n; i    ) heap.push({1, i});
    for (int i = 1; i <= n; i    )
    {
        Node t = heap.top();
        heap.pop();
        tmp[i] = a[t.i]   b[t.j];
        heap.push({t.i   1, t.j});
    }
    memcpy(a, tmp, sizeof tmp);
}

数据备份

题目描述

你在一家 IT 公司为大型写字楼或办公楼的计算机数据做备份。

然而数据备份的工作是枯燥乏味的，因此你想设计一个系统让不同的办公楼彼此之间互相备份，而你则坐在家中尽享计算机游戏的乐趣。

已知办公楼都位于同一条街上，你决定给这些办公楼配对（两个一组）。

每一对办公楼可以通过在这两个建筑物之间铺设网络电缆使得它们可以互相备份。

然而，网络电缆的费用很高。

当地电信公司仅能为你提供

K

条网络电缆，这意味着你仅能为

K

对办公楼（总计

2K

个办公楼）安排备份。

任意一个办公楼都属于唯一的配对组（换句话说，这

2K

个办公楼一定是相异的）。

此外，电信公司需按网络电缆的长度（公里数）收费。

因而，你需要选择这

K

对办公楼使得电缆的总长度尽可能短。

换句话说，你需要选择这

K

对办公楼，使得每一对办公楼之间的距离之和（总距离）尽可能小。

下面给出一个示例，假定你有

5

个客户，其办公楼都在一条街上。

这

5

个办公楼分别位于距离大街起点

1km,3km,4km,6km

和

12km

处。

电信公司仅为你提供

K=2

条电缆。

最好的配对方案是将第 1 个和第 2 个办公楼相连，第 3 个和第 4 个办公楼相连。

这种配对方案需要总长

4km

的网络电缆，满足距离之和最小的要求。

输入格式

第一行输入整数

n

和

K

，其中

n

表示办公楼的数目，

K

表示可利用的网络电缆的数目。

接下来的

n

行每行仅包含一个整数

s

，表示每个办公楼到大街起点处的距离。

这些整数将按照从小到大的顺序依次出现。

输出格式

输出应由一个正整数组成，给出将

2K

个相异的办公楼连成

K

对所需的网络电缆的最小总长度。

数据范围

2≤n≤100000, 1≤K≤n/2, 0≤s≤10^9

输入样例：

代码语言：javascript复制

5 2 
1
3
4
6
12

输出样例：

代码语言：javascript复制

4

解析

显然，在最优解中选出的一对点，一定是相邻的

不妨设，相邻点之间的距离为

D_1, D_2, cdots, D_{n-1}

k = 1

时，答案显然是

D

数列中的最小值

k = 2

时，设

D_i

为数列中的最小值，接下来分类讨论选不选

D_i

情况下的最优策略：

1. 选了最小值

D_i

，以及不是

D_{i-1}

也不是

D_{i 1}

之外其他数中的最小值

1. 没选最小值

D_i

，选了最小值两侧的

D_{i-1}

和

D_{i 1}

第一种情况显然；对于第二种情况，如果只选了

D_{i-1}

和

D_{i 1}

两者之一，再加一个其他数中的最小值，则不选

D_{i-1}

或

D_{i 1}

，改为选

D_i

方案不会变差，因此得证两种情况下，该选法一定最优

根据上述的

D_{i-1}, D_i, D_{i 1}

选法的互斥性，我们可以先选上数列中的最小值

D_i

，然后将数列中的

D_{i-1}, D_i, D_{i 1}

替换成一个

D

其权值为

D_{i-1} D_{i 1} - D_i

，即如果我们第二轮选上这个点，就代表走了

k=2

时的情况二，不选就是情况一

于是，我们就可以用一个双向链表 小根堆来模拟上述最优策略了

代码语言：javascript复制

while (m)
{
    PII t = heap.top(); heap.pop();
    
    if (t.x != node[t.y].value) continue;
    
    res  = t.x;
    LL v = -t.x;
    v  = node[node[t.y].prev].value;
    v  = node[node[t.y].next].value;
    heap.push({v, insert(node[t.y].next, v)});
    
    remove(node[t.y].prev);
    remove(node[t.y].next);
    remove(t.y);
    m -- ;
}

合并果子

题目描述

在一个果园里，达达已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。

达达决定把所有的果子合成一堆。

每一次合并，达达可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。

可以看出，所有的果子经过

n−1

次合并之后，就只剩下一堆了。

达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以达达在合并果子时要尽可能地节省体力。

假定每个果子重量都为

1

，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使达达耗费的体力最少，并输出这个最小的体力耗费值。

输入格式

输入包括两行，第一行是一个整数

n

，表示果子的种类数。

第二行包含

n

个整数，用空格分隔，第

i

个整数

a_i

是第

i

种果子的数目。

输出格式

输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。

输入数据保证这个值小于

231

。

数据范围

1≤n≤10000, 1≤a_i≤20000

输入样例：

代码语言：javascript复制

3 
1 2 9 

输出样例：

代码语言：javascript复制

15

解析

Huffman Tree 太经典了，就不多写什么了

代码语言：javascript复制

int res = 0;
while (heap.size() > 1)
{
    int a = heap.top(); heap.pop();
    int b = heap.top(); heap.pop();
    res  = a   b;
    heap.push(a   b);
}

荷马史诗

题目描述

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

达达最近迷上了文学。

她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。

但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了，达达想通过一种编码方式使得它变得短一些。

一部《荷马史诗》中有

n

种不同的单词，从

1

到

n

进行编号。其中第

i

种单词出现的总次数为

w_i

。

达达想要用

k

进制串

s_i

来替换第

i

种单词，使得其满足如下要求:

对于任意的

1≤i,j≤n quad (i≠j)

，都有：

s_i

不是

s_j

的前缀。

现在达达想要知道，如何选择

s_i

，才能使替换以后得到的新的《荷马史诗》长度最小。

在确保总长度最小的情况下，达达还想知道最长的

s_i

的最短长度是多少？

一个字符串被称为

k

进制字符串，当且仅当它的每个字符是

0

到

k−1

之间（包括

0

和

k−1

）的整数。

字符串

Str1

被称为字符串

Str2

的前缀，当且仅当：存在

1≤t≤m

，使得

Str1=Str2[1..t]

。

其中，

m

是字符串

Str2

的长度，

Str2[1..t]

表示

Str2

的前

t

个字符组成的字符串。

注意:请使用

64

位整数进行输入输出、储存和计算。

输入格式

输入文件的第

1

行包含

2

个正整数

n,k

，中间用单个空格隔开，表示共有

n

种单词，需要使用

k

进制字符串进行替换。

第

2∼n 1

行：第

i 1

行包含

1

个非负整数

w_i

，表示第

i

种单词的出现次数。

输出格式

输出文件包括 2 行。

第 1 行输出 1 个整数，为《荷马史诗》经过重新编码以后的最短长度。

第 2 行输出 1 个整数，为保证最短总长度的情况下，最长字符串 si 的最短长度。

数据范围

2≤n≤100000, 2≤k≤9, 1≤wi≤10^{12}

输入样例：

代码语言：javascript复制

4 2
1
1
2
2

输出样例：

代码语言：javascript复制

12
2

解析

如果每轮合并的石子 可以是任意 的 两堆 石子，那么用到的就是经典的 Huffman Tree 的二叉堆模型

如果每轮合并的石子 可以是任意 的

k

堆 石子，那么用到的就是经典的 Huffman Tree 的

k

叉堆模型

也是太经典了，就不多介绍了，记得需要填空结点，使得

k - 1 mid n - 1

二叉堆中，由于

k-1 = 1

，

1

能整除一切正整数，所有不需要关心这一问题

代码语言：javascript复制

for (;(n - 1) % (k - 1); n    ) heap.push({0, 0});
ULL res = 0;
while (heap.size() > 1)
{
    ULL s = 0; int height = -1;
    for (int i = 1; i <= k; i    )
    {
        auto t = heap.top(); heap.pop();
        s  = t.x;
        if (height == -1 || height < t.y) height = t.y;
    }
    res  = s;
    heap.push({s, height   1});
}

二叉树 编程算法

0 人点赞