朝花中学OI队的奋斗历程——浅谈单调队列

问题背景

朝花中学是市里有名的OI强校，每年朝花中学都要选一名队员代表学校参加市里的OI联赛，这名参赛队员可从初一到高二的所有选手中选拔（高三不能比赛……）。校队教练nomelteews想要给这些高手更好的培养机会，于是决定成立朝花集训队，给予集训队里的选手以特殊指导，并直接从集训队中选队员参加联赛。

为了保证教学效果，nomelteews要始终让集训队的总人数最少，但每年比赛时又必须从队里挑出全校最强的队员参赛。nomelteews每年只能从初一新生中选拔集训队新队员，那么，应吸纳哪些人入队呢？

问题思路

nomelteews每年对申请入队的初一新生进行一次综合能力测评，以测评成绩作为判断OI能力强弱的依据。下面是部分测评成绩表。

最简单的想法就是——让所有人入队！但是这显然不能满足总人数最少的要求。

进一步的想法是，让每年成绩最好的人入队。例如2013年的3名选手中，ugoul的成绩最好，就在这三人中选ugoul入队。理由是，只要是ayohs和anuzan能参加的比赛，ugoul也能参加；而ugoul的能力比ayohs和anuzan都强，所以有理由淘汰ayohs和anuzan。

那么按这个思路，剩下的人就是：

这样队里最多同时有5人，每年最早入队的人会退役，参加比赛时只要从5人中找出能力最强的人就好了，看起来效率相当不错。

那么，队的人数能不能更少呢？一个大胆的想法是，只留当前遇到的最强的队员在队里！那么队里的情况就是：

然而，如果按这个标准选拔，由于最强的ugoul必须在2017年末退役，因此2018年的比赛只能由当年最强的ukim（460分）来比赛。按照上一个方案，2018年的比赛可以由ikat（500分）参赛，显然如果采用这个方案，最强的队员退役后会造成尴尬局面。

还有什么办法吗？大自然的法则——优胜劣汰也许能给我们一点启示。我们来一年一年看。

2012年，只有evets申请入队，无疑只能让evets一人进队。那么2012年的比赛当然就由他来参加啦！

2013年，当年最强的是ugoul。此时，我们可以淘汰evets。为什么呢？2013年以后，evets只能参加2013_{2016年的比赛，而ugoul却能参加2013}2017年的比赛，也就是说凡是evets可以参加的比赛，ugoul都可以参加；而ugoul又比evets强，因此淘汰evets。当年的比赛由ugoul参加。

2014年，当年最强的是ikat。ikat没有ugoul强，他能不能入队呢？我们来看：ugoul能参加2014_{2017年的比赛，而ikat能参加2014}2018年的比赛，ikat能参加的比赛比ugoul多，因此仍要接纳ikat入队。事实上，根据我们先前的判断，2018年的比赛是要由ikat参加的。但是2014年的比赛还是要由队里最强的ugoul参加。

2015年，类似以上讨论，okohs可以入队。而当年的比赛仍然由ugoul参加（队霸大佬）。

2016年，ahustim（480分）入队。她要淘汰okohs，因为okohs她虽然能力和ahustim相同，但是比ahustim早退役（还是那句话，凡是okohs能参加的比赛ahustim都能参加），因此okohs只好提前退役了。当年的比赛由ugoul参加。

2017年队里的情况如下：

到了2018年，队里的情况有变——ugoul退役了！这样当年的比赛就要让ikat参加了。当年情况如下：

问题总结

仔细观察这些表格，我们发现，这些表格具有以下特点：

①每年只有一人入队；②队里队员的成绩总是随着年份的增加而单调递减；③每年总是由最老的队员（当然也是最强的）参赛；④每年只有最多1人——最老的队员退役。

这个集训队其实具有类似（双端）队列的结构——每年新队员加入时从队尾淘汰，从队尾入队；每年参赛时取队头；每年退役时只有队头退役；而它又具有单调递减的特殊性，因此我们把这样的队列称为单调队列。

单调队列有什么作用呢？它可以解决下面被称为“滑动窗口”的问题。

如下图，给出一个长度为n的序列A，求A中所有长度为m的连续子序列的最大值。下图中假设n=7，m=3。

这题只需枚举每个连续子序列，使用单调队列得出最大值即可。我们看看单调队列是怎么工作的。

这个集训队每年在做的事情就是单调队列的操作。

1. 入队/滑动窗口右滑。每年选拔新队员时，淘汰比这名新队员弱的老队员。对于单调队列，就是插入新元素时，把先前存在的比当前元素小的元素弹出（从队尾退队）。
2. 退役/滑动窗口右滑。只需判断最老的队员是否需要退队。对于单调队列，只需判断队头是否已经超出滑动窗口范围，若超出，则从队头退队。
3. 参赛/查询滑动窗口最大值。直接派最老的队员参赛/直接返回队头元素。

我们手工模拟一下这个单调队列的工作过程吧（如下表）！

分析单调队列的时间复杂度，每个元素最多入队1次、出队1次，且出入队都是O(1)的，因此这是一个总时间O(n)的算法。这样相对高效的算法，能为我们解决动态规划问题提供有力的优化，例如NOIP 2017普及组的第4题就可以使用单调队列，此处不再叙述，如果有兴趣可以在理解单调队列的概念后看一看题解。

代码实现

单调队列可以用STL的deque实现，也可以手写数组实现。由于每个元素最多入队一次、出队一次，手写数组的大小只要和原数组一样就可以了（也就是和元素总数相等即可）。

下面分别给出deque实现和数组实现的C++代码，输入输出格式见单调队列模板题P1440 （当然这题也有其他不错的解法）。与上述讨论不同的是，本题输出的是滑动窗口内的最小值。

两种实现效率比较：总时间 deque 1660ms，deque(O2) 1100ms, 手写数组实现 908ms。看来有时还是需要手写数组的！

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

//deque实现
#include <cstdio>
#include <queue> // 提供deque
#define MAXN 2000005
using namespace std;

struct Num{
    int index,x;//需要记录单调队列内每个数的入队时间(index)和大小(x)
};

int a[MAXN]; //原数组
deque<Num> q; //单调队列 

int main(void){
    int n,m; //n表示序列长度，m表示滑动窗口长度
    Num t;//保存当前元素
    //输入
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    //问题解决
    for (int i=1;i<=n;i++){
        //先输出数a[i]前的最小值
        if (q.empty()) //q空，即a[i]前没有元素
            printf("0\n");
        else { //否则判断队头是否需要出队并输出范围内的队头
            if (q.front().index+m<i) //队头已经超出滑动窗口范围
                q.pop_front(); // 弹出队头
            printf("%d\n",q.front().x); //此时队一定非空（想想为什么）
        }
        while ((!q.empty()) && q.back().x>=a[i]) 
        //当队列非空时，不断弹出队尾比当前元素大的元素
            q.pop_back();
        t.index=i;
        t.x=a[i];
        q.push_back(t);//将当前元素入队
        //注意：当前元素无论如何都会入队（想想为什么）
    }
    return 0;
}

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

//数组实现
#include <cstdio>
#define MAXN 2000005
using namespace std;

struct Num{
    int index,x;//需要记录单调队列内每个数的入队时间(index)和大小(x)
};

int a[MAXN]; //原数组
Num q[MAXN]; //单调队列 

int main(void){
    int n,m; //n表示序列长度，m表示滑动窗口长度
    int front,back; //front,back分别表示队头、队尾位置
    //输入
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    //问题解决
    front=1;
    back=0;//初始化队头队尾位置，队头>队尾表示队空
    for (int i=1;i<=n;i++){
        //先输出数a[i]前的最小值
        if (front>back) //q空，即a[i]前没有元素
            printf("0\n");
        else { //否则判断队头是否需要出队并输出范围内的队头
            if (q[front].index+m<i) //队头已经超出滑动窗口范围
                front++; // 弹出队头
            printf("%d\n",q[front].x); //此时队一定非空（想想为什么）
        }
        while (front<=back && q[back].x>=a[i]) 
        //当队列非空时，不断弹出队尾比当前元素大的元素
            back--;
        back++;
        q[back].x=a[i];
        q[back].index=i;//将当前元素入队
        //注意：当前元素无论如何都会入队（想想为什么）
    }
    return 0;
}

练习与最后的废话

涉及单调队列的题目直接在洛谷搜索就可以找到一些,这两题（P1886 滑动窗口和P1440 求m区间内的最小值）是模板题。（但是“P2952 牛线”不是单调队列的题目！）

其实多重背包问题（有$n$种物品，每种物品有$a_{i}$个，每种物品的价值为$w_{i}$，每种物品的体积为$v_{i}$，现有一个容量为$C$的背包，要求装进背包里的物品的总体积不超过$C$，求装入背包的物品的总价值的最大值）的优化也可以用到单调队列，使用后时间复杂度变为O(VN)。可参考这篇文章。

其实朝花中学有必要考虑换个教练了～大家有没有发现，这个教练有两个问题：其一，进队后队员的水平并没有得到提升，和刚进队时完全一样；其二，招来的队员水平在单调递减……

相比之下，我们都是幸运的。朝花中学队员们的水平在入队后就无法改变，而我们在加入了OIer的队伍后，依然可以通过学习，不断提高自己的知识水平。因此，我们真的要珍惜学习的机会啊！

最后还是祝愿大家成为像ugoul一样的队霸大佬！