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

### 问题背景 朝花中学是市里有名的OI强校，每年朝花中学都要选**一名**队员代表学校参加市里的OI联赛，这名参赛队员可从初一到高二的所有选手中选拔（高三不能比赛……）。校队教练nomelteews想要给这些高手更好的培养机会，于是决定成立朝花集训队，给予集训队里的选手以特殊指导，并直接从集训队中选队员参加联赛。 为了保证教学效果，nomelteews要始终让集训队的总人数最少，但每年比赛时又必须从队里挑出全校最强的队员参赛。nomelteews每年只能从初一新生中选拔集训队新队员，那么，应吸纳哪些人入队呢？ ### 问题思路 nomelteews每年对申请入队的初一新生进行一次综合能力测评，以测评成绩作为判断OI能力强弱的依据。下面是部分测评成绩表。 | 年份 | 姓名 | 成绩 | | :----------: | :----------: | :----------: | | 2012 | evets | 450 | | 2013 | ayohs | 420 | | 2013 | ugoul | 520 | | 2013 | anuzan | 350 | | 2014 | ikat | 500 | | 2014 | xela | 460 | | 2015 | okohs | 480 | | 2015 | repeerc | 400 | | 2016 | ahustim | 480 | | 2016 | umier | 440 | | 2017 | amnem | 470 | | 2017 | natnij | 430 | | 2018 | ukim | 460 | | 2018 | ilib | 450 | 最简单的想法就是——让所有人入队！但是这显然不能满足总人数最少的要求。 进一步的想法是，让每年成绩最好的人入队。例如2013年的3名选手中，ugoul的成绩最好，就在这三人中选ugoul入队。理由是，只要是ayohs和anuzan能参加的比赛，ugoul也能参加；而ugoul的能力比ayohs和anuzan都强，所以有理由淘汰ayohs和anuzan。 那么按这个思路，剩下的人就是： | 年份 | 姓名 | 成绩 | | :----------: | :----------: | :----------: | | 2012 | evets | 450 | | 2013 | ugoul | 520 | | 2014 | ikat | 500 | | 2015 | okohs | 480 | | 2016 | ahustim | 480 | | 2017 | amnem | 470 | | 2018 | ukim | 460 | 这样队里最多同时有5人，每年最早入队的人会退役，参加比赛时只要从5人中找出能力最强的人就好了，看起来效率相当不错。 那么，队的人数能不能更少呢？一个大胆的想法是，只留当前遇到的最强的队员在队里！那么队里的情况就是： | 年份 | 队员 | 成绩 | | :----------: | :----------: | :----------: | | 2012 | evets | 450 | | 2013-2017 | ugoul | 520 | | 2018 | ukim | 460 | 然而，如果按这个标准选拔，由于最强的ugoul必须在2017年末退役，因此2018年的比赛只能由当年最强的ukim（460分）来比赛。按照上一个方案，2018年的比赛可以由ikat（500分）参赛，显然如果采用这个方案，最强的队员退役后会造成尴尬局面。 还有什么办法吗？大自然的法则——优胜劣汰也许能给我们一点启示。我们来一年一年看。 2012年，只有evets申请入队，无疑只能让evets一人进队。那么2012年的比赛当然就由他来参加啦！ | 入队年份 | 队员 | 成绩 | 参赛(\*) | | :----------: | :----------: | :----------: | | 2012 | evets | 450 | \* | 2013年，当年最强的是ugoul。此时，我们可以淘汰evets。为什么呢？2013年以后，evets只能参加2013~2016年的比赛，而ugoul却能参加2013~2017年的比赛，也就是说凡是evets可以参加的比赛，ugoul都可以参加；而ugoul又比evets强，因此淘汰evets。当年的比赛由ugoul参加。 | 入队年份 | 队员 | 成绩 | 参赛(\*) | | :----------: | :----------: | :----------: | | 2013 | ugoul | 520 | \* | 2014年，当年最强的是ikat。ikat没有ugoul强，他能不能入队呢？我们来看：ugoul能参加2014~2017年的比赛，而ikat能参加2014~2018年的比赛，ikat能参加的比赛比ugoul多，因此仍要接纳ikat入队。事实上，根据我们先前的判断，2018年的比赛是要由ikat参加的。但是2014年的比赛还是要由队里最强的ugoul参加。 | 入队年份 | 队员 | 成绩 | 参赛(\*) | | :----------: | :----------: | :----------: | | 2013 | ugoul | 520 | \* | | 2014 | ikat | 500 | &nbsp; | 2015年，类似以上讨论，okohs可以入队。而当年的比赛仍然由ugoul参加（~~队霸~~大佬）。 | 入队年份 | 队员 | 成绩 | 参赛(\*) | | :----------: | :----------: | :----------: | | 2013 | ugoul | 520 | \* | | 2014 | ikat | 500 | &nbsp; | | 2015 | okohs | 480 | &nbsp; | 2016年，ahustim（480分）入队。她要淘汰okohs，因为okohs她虽然能力和ahustim相同，但是比ahustim早退役（还是那句话，凡是okohs能参加的比赛ahustim都能参加），因此okohs只好提前退役了。当年的比赛由ugoul参加。 | 入队年份 | 队员 | 成绩 | 参赛(\*) | | :----------: | :----------: | :----------: | | 2013 | ugoul | 520 | \* | | 2014 | ikat | 500 | &nbsp; | | 2016 | ahustim | 480 | &nbsp; | 2017年队里的情况如下： | 入队年份 | 队员 | 成绩 | 参赛(\*) | | :----------: | :----------: | :----------: | | 2013 | ugoul | 520 | \* | | 2014 | ikat | 500 | &nbsp; | | 2016 | ahustim | 480 | &nbsp; | | 2017 | amnem | 470 | &nbsp; | 到了2018年，队里的情况有变——ugoul退役了！这样当年的比赛就要让ikat参加了。当年情况如下： | 入队年份 | 队员 | 成绩 | 参赛(\*) | | :----------: | :----------: | :----------: | | 2014 | ikat | 500 | \* | | 2016 | ahustim | 480 | &nbsp; | | 2017 | amnem | 470 | &nbsp; | | 2018 | ukim | 460 | &nbsp; | ### 问题总结 仔细观察这些表格，我们发现，这些表格具有以下特点： ①每年只有一人入队；②队里队员的成绩总是随着年份的增加而单调递减；③每年总是由最老的队员（当然也是最强的）参赛；④每年只有最多1人——最老的队员退役。 这个集训队其实具有类似（双端）队列的结构——每年新队员加入时从队尾淘汰，从队尾入队；每年参赛时取队头；每年退役时只有队头退役；而它又具有单调递减的特殊性，因此我们把这样的队列称为**单调队列**。 单调队列有什么作用呢？它可以解决下面被称为“滑动窗口”的问题。 如下图，给出一个长度为n的序列A，求A中所有长度为m的连续子序列的最大值。下图中假设n=7，m=3。  这题只需枚举每个连续子序列，使用单调队列得出最大值即可。我们看看单调队列是怎么工作的。 这个集训队每年在做的事情就是单调队列的操作。 1. 入队/滑动窗口右滑。每年选拔新队员时，淘汰比这名新队员弱的老队员。对于单调队列，就是插入新元素时，把先前存在的比当前元素小的元素弹出（从队尾退队）。 2. 退役/滑动窗口右滑。只需判断最老的队员是否需要退队。对于单调队列，只需判断队头是否已经超出滑动窗口范围，若超出，则从队头退队。 3. 参赛/查询滑动窗口最大值。直接派最老的队员参赛/直接返回队头元素。 我们手工模拟一下这个单调队列的工作过程吧（如下表）！ | 时刻 | 入队元素 | 入队后队列 | 最大值 | | :----------: | :----------: | :----------: | :----------: | | 1 | 5 | 5 | - | | 2 | 3 | 5 3 | - | | 3 | 2 | 5 3 2 | 5 | | 4 | 1 | 3 2 1 | 3 | | 5 | 0 | 2 1 0 | 2 | | 6 | 7 | 7 | 7 | | 7 | 8 | 8 | 8 | 分析单调队列的时间复杂度，每个元素最多入队1次、出队1次，且出入队都是O(1)的，因此这是一个总时间O(n)的算法。这样相对高效的算法，能为我们解决动态规划问题提供有力的优化，例如[NOIP 2017普及组的第4题](https://www.luogu.org/problemnew/show/P3957)就可以使用单调队列，此处不再叙述，如果有兴趣可以在理解单调队列的概念后看一看题解。 ### 代码实现 单调队列可以用STL的deque实现，也可以手写数组实现。由于每个元素最多入队一次、出队一次，手写数组的大小只要和原数组一样就可以了（也就是和元素总数相等即可）。 下面分别给出deque实现和数组实现的C++代码，输入输出格式见[单调队列模板题P1440](https://www.luogu.org/problemnew/show/P1440) （当然这题也有其他不错的解法）。与上述讨论不同的是，本题输出的是滑动窗口内的最**小**值。 两种实现效率比较：总时间 deque 1660ms，deque(O2) 1100ms, 手写数组实现 908ms。看来有时还是需要手写数组的！ ```cpp //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; } ``` ```cpp //数组实现 #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; } ``` ### 练习~~与最后的废话~~ 涉及单调队列的题目直接在洛谷[搜索](https://www.luogu.org/problemnew/lists?orderitem=difficulty&tag=56)就可以找到一些,这两题（[P1886 滑动窗口](https://www.luogu.org/problemnew/show/P1886)和[P1440 求m区间内的最小值](https://www.luogu.org/problemnew/show/P1440)）是模板题。（但是“P2952 牛线”不是单调队列的题目！） 其实多重背包问题（有$n$种物品，每种物品有$a_{i}$个，每种物品的价值为$w_{i}$，每种物品的体积为$v_{i}$，现有一个容量为$C$的背包，要求装进背包里的物品的总体积不超过$C$，求装入背包的物品的总价值的最大值）的优化也可以用到单调队列，使用后时间复杂度变为O(VN)。可参考[这篇文章](https://blog.csdn.net/FSAHFGSADHSAKNDAS/article/details/52825227)。 其实朝花中学有必要考虑换个教练了～大家有没有发现，这个教练有两个问题：其一，进队后队员的水平并没有得到提升，和刚进队时完全一样；其二，招来的队员水平在单调递减…… 相比之下，我们都是幸运的。朝花中学队员们的水平在入队后就无法改变，而我们在加入了OIer的队伍后，依然可以通过学习，不断提高自己的知识水平。因此，我们真的要珍惜学习的机会啊！ 最后还是祝愿大家成为像ugoul一样的~~队霸~~大佬！