Sweetlemon
2018-07-15 23:21:00
朝花中学是市里有名的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 |
2015年，类似以上讨论，okohs可以入队。而当年的比赛仍然由ugoul参加（队霸大佬）。
| 入队年份 | 队员 | 成绩 | 参赛(*) |
|---|---|---|---|
| 2013 | ugoul | 520 | * |
| 2014 | ikat | 500 | |
| 2015 | okohs | 480 |
2016年，ahustim（480分）入队。她要淘汰okohs，因为okohs她虽然能力和ahustim相同，但是比ahustim早退役（还是那句话，凡是okohs能参加的比赛ahustim都能参加），因此okohs只好提前退役了。当年的比赛由ugoul参加。
| 入队年份 | 队员 | 成绩 | 参赛(*) |
|---|---|---|---|
| 2013 | ugoul | 520 | * |
| 2014 | ikat | 500 | |
| 2016 | ahustim | 480 |
2017年队里的情况如下：
| 入队年份 | 队员 | 成绩 | 参赛(*) |
|---|---|---|---|
| 2013 | ugoul | 520 | * |
| 2014 | ikat | 500 | |
| 2016 | ahustim | 480 | |
| 2017 | amnem | 470 |
到了2018年，队里的情况有变——ugoul退役了！这样当年的比赛就要让ikat参加了。当年情况如下：
| 入队年份 | 队员 | 成绩 | 参赛(*) |
|---|---|---|---|
| 2014 | ikat | 500 | * |
| 2016 | ahustim | 480 | |
| 2017 | amnem | 470 | |
| 2018 | ukim | 460 |
仔细观察这些表格，我们发现，这些表格具有以下特点：
①每年只有一人入队；②队里队员的成绩总是随着年份的增加而单调递减；③每年总是由最老的队员（当然也是最强的）参赛；④每年只有最多1人——最老的队员退役。
这个集训队其实具有类似（双端）队列的结构——每年新队员加入时从队尾淘汰，从队尾入队；每年参赛时取队头；每年退役时只有队头退役；而它又具有单调递减的特殊性，因此我们把这样的队列称为单调队列。
单调队列有什么作用呢？它可以解决下面被称为“滑动窗口”的问题。
如下图，给出一个长度为n的序列A，求A中所有长度为m的连续子序列的最大值。下图中假设n=7，m=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题就可以使用单调队列，此处不再叙述，如果有兴趣可以在理解单调队列的概念后看一看题解。
单调队列可以用STL的deque实现，也可以手写数组实现。由于每个元素最多入队一次、出队一次，手写数组的大小只要和原数组一样就可以了（也就是和元素总数相等即可）。
下面分别给出deque实现和数组实现的C++代码，输入输出格式见单调队列模板题P1440 （当然这题也有其他不错的解法）。与上述讨论不同的是，本题输出的是滑动窗口内的最小值。
两种实现效率比较：总时间 deque 1660ms，deque(O2) 1100ms, 手写数组实现 908ms。看来有时还是需要手写数组的！
//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;
}//数组实现
#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 牛线”不是单调队列的题目！）
其实多重背包问题（有
其实朝花中学有必要考虑换个教练了～大家有没有发现，这个教练有两个问题：其一，进队后队员的水平并没有得到提升，和刚进队时完全一样；其二，招来的队员水平在单调递减……
相比之下，我们都是幸运的。朝花中学队员们的水平在入队后就无法改变，而我们在加入了OIer的队伍后，依然可以通过学习，不断提高自己的知识水平。因此，我们真的要珍惜学习的机会啊！
最后还是祝愿大家成为像ugoul一样的队霸大佬！