单调队列及其应用
关键字
队列，合并果子，窗户，广告印刷，最长XX子序列，志愿者选拔，动态规划，烽火传递
正文
单调队列，望文生义，就是指队列中的元素是单调的。如：{a1,a2,a3,a4……an}满足a1<=a2<=a3……<=an,a序列便是单调递增序列。同理递减队列也是存在的。
单调队列的出现可以简化问题，队首元素便是最大（小）值，这样，选取最大（小）值的复杂度便为o（1），由于队列的性质，每个元素入队一次，出队一次，维护队列的复杂度均摊下来便是o（1）。
如何维护单调队列呢，以单调递增序列为例：
1、如果队列的长度一定，先判断队首元素是否在规定范围内，如果超范围则增长对首。
2、每次加入元素时和队尾比较，如果当前元素小于队尾且队列非空，则减小尾指针，队尾元素依次出队，直到满足队列的调性为止
要特别注意头指针和尾指针的应用。
下面介绍单调队列的具体应用：
一、单调队列的直接应用
1.合并果子
【问题描述】
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有3种果子，数目依次为1，2，9。可以先将 1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
【输入文件】
输入文件fruit.in包括两行，第一行是一个整数n（1 <= n <= 10000），表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai（1 <= ai <= 20000）是第i种果子的数目。
【输出文件】
输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。
【样例输入】
3
1 2 9
【样例输出】
15
【数据规模】
对于30%的数据，保证有n <= 1000；
对于50%的数据，保证有n <= 5000；
对于全部的数据，保证有n <= 10000。
分析:
这个题目非常的经典，发放也很多，可以采用快排或者堆，其思想都是选取当前最小的两个堆进行合并。复杂度均为O(nlogn)，如果用有序队列维护，时间复杂度为O（n）。
每次选取进行合并的两堆，不是最先给定的堆，就是合并最初堆若干次后得到的新堆，所以需要维护两个单调递增队列，一个队列存最初给定的堆的值（1），一个存合并后得到的新值（2）。
每次选择时有三种状态：
1、 选取队一的队首两个 2、选取队2的的队首两个 3、选取二者队首各一个
只需对每个队列的指针做相应的更改。
特别注意初始化。
这道题很好的运用了题目中决策的单调性，对初始对经行排序，保证了其单调性。而对于新产生的堆来说，一旦有新元素加入其中，则新元素一定大于原有元素。（很显然，由于队列1的单调性）。
也就是说，队列的单调性是自然而然的。是不需要维护的。要善于观察分析，才能发现。
Code
program liukee;
var
a,b:array[1..100000] of longint;
h1,h2,t2,temp,n,i,ans:longint;
function min(a,b,c:longint):longint;
begin
if a<b then min:=a
else min:=b;
if c<min then min:=c;
end;
procedure sort(l,r:longint);
var
i,j,mid,temp:longint;
begin
i:=l;
j:=r;
mid:=a[l+random(r-l)];//随机化排序
repeat
while a[i]<mid do inc(i);
while a[j]>mid do dec(j);
if i<=j then
begin
temp:=a[i];
a[i]:=a[j];
a[j]:=temp;
inc(i);
dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
begin
randomize;
readln(n);
for i:=1 to n do
read(a[i]);
for i:=1 to n do
b[i]:=maxlongint>>2;//保证程序在需要的地方停止，由于要选极小值
sort(1,n);
a[n+1]:=maxlongint>>2;//作用同上
a[n+2]:=maxlongint>>2;
h1:=1;
h2:=1;
t2:=0;
for i:=1 to n-1 do
begin
temp:=min(a[h1]+a[h1+1],a[h1]+b[h2],b[h2]+b[h2+1]);
if temp=a[h1]+a[h1+1] then inc(h1,2)
else if temp=a[h1]+b[h2] then begin inc(h1);inc(h2);end
else inc(h2,2);
inc(t2);
b[t2]:=temp;
inc(ans,temp);
end;
writeln(ans);
end.
2．Window
给定你n个数ai~an一个确定长度的区间，让你求出每个区间内的最大值，并按照顺序输出
输入
N，k
A1~an
输出
每个区间内的最大值
分析
由于该题的区间长度一定，我们可以用一个长度为k（A,B）的队列来维护数据的有序性。
剩下的问题就是如何维护队列的有序性了。
最前面已经说到了，代码也不再赘余。
3、志愿者选拔(foj 1894)
世博会马上就要开幕了，福州大学组织了一次志愿者选拔活动。
参加志愿者选拔的同学们排队接受面试官们的面试。参加面试的同学们按照先来先面试并且先结束的原则接受面试官们的考查。
面试中每个人的人品是主要考查对象之一。（提高人品的方法有扶老奶奶过街，不闯红灯等）
作为主面试官的John想知道当前正在接受面试的同学队伍中人品值最高的是多少。于是他请你帮忙编写一个程序来计算。
Input
输入数据第一行为一整数T，表示有T组输入数据。
每组数据第一行为”START”，表示面试开始
接下来的数据中有三种情况：
![clip_image002[4]](http://images.cnblogs.com/cnblogs_com/liukeke/201106/201106131611266561.png "clip_image002[4]")
1 C NAME RP_VALUE 名字为NAME的人品值为RP_VALUE的同学加入面试队伍。(名字长度不大于5，0 <= RP_VALUE <= 1,000,000,000)
2 G 排在面试队伍最前面的同学面试结束离开考场。
3 Q 主面试官John想知道当前正在接受面试的队伍中人品最高的值是多少。
最后一行为”END”，表示所有的面试结束，面试的同学们可以依次离开了。
所有参加面试的同学总人数不超过1,000,000
Output
对于每个询问Q,输出当前正在接受面试的队伍中人品最高的值,如果当前没有人正在接受面试则输出-1。
Sample Input
2
START
C Tiny 1000000000
C Lina 0
Q
G
Q
END
START
Q
C ccQ 200
C cxw 100
Q
G
Q
C wzc 500
Q
END
Sample Output
1000000000
0
-1
200
100
分析：
题目本身就是队列，由于要找的是最大值，我们自然想到用单调队列解决问题。
维护一个单调递减序列，只需输出序列中的第一个元素即可。
对于命令我们可以进行不同的处理：
如果是Q命令，则判断当前队列中是否仍有元素，如果没有则输出-1，如果有则直接输出队首。
如果是G命令，则对last加1，之后对于队列中所有超出范围的前端元素进行出队操作。（该元素在原序列中的位置>=last）
如果是C命令，则将该元素加入队列中，并和队尾元素比较，维护队列的单调性。
这里考虑一个问题，当前元素加如后对队尾元素为什么可以毫无保留的删去呢？
因为当前加入的元素比队尾元素大，且该元素比队尾元素入队晚（也就是该元素比队尾元素晚出队），所以只要该元素在队列中，就一定不会选取队尾元素。也就是当前状态一定比队尾元素的状态更优。——这里一定要理解深刻，这是队列的本质。
因此，这题的单调队列中维护的一个属性是元素的价值，一个属性是单调队列中的元素在原序列中的位置。
注意，q中的值是该元素在原序列中的位置！
Code
program liukeke;
var
a,q:array[0..1000000] of longint;
zu,i,l,r,last,tt,w:longint;
s:string;
begin
readln(zu);
for i:=1 to zu do
begin
tt:=0;
fillchar(a,sizeof(a),0);
readln(s);
l:=1;
r:=0;
last:=0;
原文链接：https://blog.csdn.net/weixin_30861459/article/details/94921277
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。
