《算法竞赛进阶指南》0x12 队列

队列的基础概念

队列的逻辑存储结构属于 “受限线性表”，其 “受限” 的部分是只能在线性表的一端执行插入在另一端执行删除操作

队列的修改是按照 先进先出 的原则进行的，因此队列通常被称为是 先进先出（first in first out）表，简称 FIFO 表

通常，允许插入的一端称为 “队尾”，允许删除的一端称为 “队首”

物理存储实现 可以在 C++ 中用一个数组和两个变量（记录队首队尾位置）来实现队列存储

队列多次出队操作可能会造成大量的内存浪费，因此还引入了 循环队列，从而重复利用曾被战过的空间，C++ STL 中的 queue 就是一个 循环队列

队列还有很多变体，例如两端都能取出或插入元素的双端队列 deque，以及给每个元素附带一个评估值、出队时取出估值最大的、贾登峪一个二叉堆的优先队列 priority_queue

队列也是实现广度优先搜索的基本结构

C++ STL 中的队列

C++ 在 STL 中提供了一个容器 std::queue，使用前需要先引入 <queue> 头文件。

STL 中对 queue 的定义

// clang-format off
template<
    class T,
    class Container = std::deque<T>
> class queue;

T 为 queue 中要存储的数据类型。

Container 为用于存储元素的底层容器类型。如果不指定，则默认使用 std::deque 作为底层容器。

STL 中的 queue 容器提供了一众成员函数以供调用。其中较为常用的有：

• 元素访问
  • q.front() 返回队首元素
  • q.back() 返回队尾元素
• 修改
  • q.push() 在队尾插入元素
  • q.pop() 弹出队首元素
• 容量
  • q.empty() 队列是否为空
  • q.size() 返回队列中元素的数量

此外，queue 还提供了一些运算符。较为常用的是使用赋值运算符 = 为 queue 赋值

习题

小组队列

题目描述

有

个小组要排成一个队列，每个小组中有若干人。

当一个人来到队列时，如果队列中已经有了自己小组的成员，他就直接插队排在自己小组成员的后面，否则就站在队伍的最后面。

请你编写一个程序，模拟这种小组队列。

输入格式：

输入将包含一个或多个测试用例。

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

。

接下来

行，每行输入一个小组描述，第一个数表示这个小组的人数，接下来的数表示这个小组的人的编号。

编号是

到

范围内的整数。

一个小组最多可包含

个人。

最后，命令列表如下。 有三种不同的命令：

1. ENQUEUE x - 将编号是 x 的人插入队列；
2. DEQUEUE - 让整个队列的第一个人出队；
3. STOP - 测试用例结束

每个命令占一行。

当输入用例 t=0 时，代表停止输入。

需注意：测试用例最多可包含

个命令，因此小组队列的实现应该是高效的：

入队和出队都需要使用常数时间。

输出样例

对于每个测试用例，首先输出一行 Scenario #k ，其中

是测试用例的编号。

然后，对于每个 DEQUEUE 命令，输出出队的人的编号，每个编号占一行。

在每个测试用例（包括最后一个测试用例）输出完成后，输出一个空行。

数据范围

输入样例：

2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 259001 259002 259003 259004 259005
6 260001 260002 260003 260004 260005 260006
ENQUEUE 259001
ENQUEUE 260001
ENQUEUE 259002
ENQUEUE 259003
ENQUEUE 259004
ENQUEUE 259005
DEQUEUE
DEQUEUE
ENQUEUE 260002
ENQUEUE 260003
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0

输出样例：

Scenario #1
101
102
103
201
202
203

Scenario #2
259001
259002
259003
259004
259005
260001

解析

用

个 queue 来维护

个小组各自的队列情况

再单独用一个 queue 来维护

个小组的组队列情况

queue<int> group[M], groups;
string op;
while (cin >> op, op != "STOP")
{
    if (op == "ENQUEUE")
    {
        int t; cin >> t;
        if (!group[id[t]].size()) groups.push(id[t]);
        group[id[t]].push(t);
    }
    else
    {
        int t = groups.front();
        cout << group[t].front() << endl;
        group[t].pop();
        if (!group[t].size()) groups.pop();
    }
}

蚯蚓

题目描述

蛐蛐国最近蚯蚓成灾了！

隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。

蛐蛐国里现在共有

只蚯蚓，第

只蚯蚓的长度为

，所有蚯蚓的长度都是非负整数，即可能存在长度为

的蚯蚓。

每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只，将其切成两段。

若有多只最长的，则任选一只。

神刀手切开蚯蚓的位置由有理数

决定。

一只长度为

的蚯蚓会被切成两只长度分别为

和

的蚯蚓。

特殊地，如果这两个数的其中一个等于

，则这个长度为

的蚯蚓也会被保留。

此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加一个非负整数

。

蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。

蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要

秒才能到来。

蛐蛐国王希望知道这

秒内的战况。

具体来说，他希望知道：

秒内，每一秒被切断的蚯蚓被切断前的长度，共有

个数。

秒后，所有蚯蚓的长度，共有

个数。

输入格式

第一行包含六个整数

，其中：

的意义参考题目描述；

均为正整数；你需要自己计算

（保证

）；

是输出参数，其含义将会在输出格式中解释。

第二行包含

个非负整数，为

，即初始时

只蚯蚓的长度。

同一行中相邻的两个数之间，恰好用一个空格隔开。

输出格式

第一行输出

个整数，按时间顺序，依次输出第

秒，第

秒，第

秒，…… 被切断蚯蚓（在被切断前）的长度。

第二行输出

个整数，输出

秒后蚯蚓的长度；需要按从大到小的顺序，依次输出排名第

，第

，第

，…… 的长度。

同一行中相邻的两个数之间，恰好用一个空格隔开。

即使某一行没有任何数需要输出，你也应输出一个空行。

请阅读样例来更好地理解这个格式。

数据范围

,

,

,

,

,

输入样例：

3 7 1 1 3 1
3 3 2

输出样例：

3 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2

解析

先考虑朴素的

做法

当

时，每轮操作相当于在一堆线段中，取出一个长度最长的线段，将其分割成两个子线段放回原堆中

当

时，每轮操作完后，除了操作产生的两个子线段，其他所有线段长度增加

等价于产生的两个子线段长度减去了

，然后给整个集合都加上

因此可以用一个变量

来维护整个集合的偏移量，集合中的数加上

才是他真正的值

这样做的时间复杂度为

但本题的

范围是

不能 Ac

考虑如何使得单次操作时间复杂度从

优化成

将动态维护的序列分成三个子序列：原序列

、分割后的左端子序列

、分割后的右端子序列

现证明: 在原序列中

，则切割后

的两个子序列

也大于

的两个 子序列

，

，对

放缩有：

，

，对

放缩有：

得证，因此不仅从集合中取出的数是单调递减的，新产生的两类数也分别随时间单调递减

因此可以维护三个单调队列分别维护

每轮比较三个队列的队首元素，弹出队首元素，按照要求分成两个新数字放到

的队尾

最终统计时，不要忘记加上偏移量

int get_max()
{
    int x = -1e9;
    if (hhx <= ttx) x = max(x, qx[hhx]);
    if (hhl <= ttl) x = max(x, ql[hhl]);
    if (hhr <= ttr) x = max(x, qr[hhr]);
    if (hhx <= ttx && x == qx[hhx]) hhx ++ ;
    else if (hhl <= ttl && x == ql[hhl]) hhl ++ ;
    else hhr ++ ;
    return x;
}
int main()
{
    scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &t);
    
    for (int i = 0; i < n; i ++ ) scanf("%d", &qx[i]);
    sort(qx, qx + n, greater<int>());
    ttx = n - 1;
    
    int delta = 0;
    for (int i = 1; i <= m; i ++ )
    {
        int x = get_max() + delta;
        delta += q;
        if (i % t == 0) printf("%d ", x);
        int templ = x * 1ll * u / v;
        int tempr = x - templ;
        templ -= delta, tempr -= delta;
        ql[ ++ ttl] = templ, qr[ ++ ttr] = tempr;
    }
    puts("");
    
    for (int i = 1; i <= n + m; i ++ )
    {
        int x = get_max();
        if (i % t == 0) printf("%d ", x + delta);
    }
    puts("");
    return 0;
}

双端队列

题目描述

达达现在碰到了一个棘手的问题，有

个整数需要排序。

达达手头能用的工具就是若干个双端队列。

她从

到

需要依次处理这

个数，对于每个数，达达能做以下两件事：

1. 新建一个双端队列，并将当前数作为这个队列中的唯一的数；
2. 将当前数放入已有的队列的头之前或者尾之后。

对所有的数处理完成之后，达达将这些队列按一定的顺序连接起来后就可以得到一个非降的序列。

请你求出最少需要多少个双端序列。

输入格式

第一行输入整数

，代表整数的个数。

接下来

行，每行包括一个整数

，代表所需处理的整数。

输出格式

输出一个整数，代表最少需要的双端队列数。

数据范围

输入样例：

6
3
6
0
9
6
3

输出样例：

2

解析

本题的思维量远大于代码实现难易度，显然正过来按照题意模拟，时间复杂度太高了，不可能完成

最终数组是有序的，这是本题的一大突破点，诱使我们从结果出发思考解法

在最优解中，每一个双端队列，元素的值一定是从小到大递增的，符合有序数组子序列性质

他们的下标是先减少后递增的 “单谷” 形式，因为之后枚举到的数要么接在队首，要么队尾

因此我们不妨对原数组先排序，然后根据下标找 “单谷” 计算最优解

本题另一大难点在于数值相同的元素在最优解中的位置（值相同可以互相交换位置，不改变有序性）

考虑一个贪心策略：

1. 如果当前处于下降趋势
   1. 下标最大值小于最后一个元素的下标，按下标降序接在后面，整体呈 \ 形
   2. 下标最大值大于最后一个元素的下标，按下标升序接在后面，整体呈 \/ 形
2. 如果当前处于上升趋势
   1. 下标最小值大于最后一个元素的下标，按下标升序接在后面，整体呈 / 形
   2. 下标最小值小于最后一个元素的下标，按下标降序接在后面，整体呈 /\ 形

这个启发式策略正确性是显然的，略证

int res = 1;
int last = n + 1, k = -1;
for (int i = 1; i <= n; )
{
    int j = i;
    while (j <= n && a[j].x == a[i].x) j ++ ;
    int max_idx = a[j - 1].y, min_idx = a[i].y;
    if (~k)  //上升
    {
        if (last < min_idx) last = max_idx;
        else last = min_idx, k = -1, res ++ ;
    }
    else    //下降
    {
        if (last > max_idx) last = min_idx;
        else last = max_idx, k = 1;
    }
    i = j;
}

最大子序和

题目描述

输入一个长度为

的整数序列，从中找出一段长度不超过

的连续子序列，使得子序列中所有数的和最大。

注意： 子序列的长度至少是

。

输入格式 第一行输入两个整数

。

第二行输入

个数，代表长度为

的整数序列。

同一行数之间用空格隔开。

输出格式

输出一个整数，代表该序列的最大子序和。

数据范围

输入样例：

6 4
1 -3 5 1 -2 3

输出样例：

7

解析

这是我以前在 DP 中写过的部分，就不在额外写 lyd 的做法了

看到求一段 连续区间 的和的问题，会想到用 前缀和 进行优化，然后就是 枚举 区间的问题

暴力枚举 子区间是一种方法，但没有优化空间；因此不妨 枚举 子区间的 右端点

状态表示-集合

：以

为 右端点，长度 不超过

连续子区间

状态表示-属性

：区间的总和最大

状态计算

：

$$ f_i =