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