(烽火传递)烽火台又称烽燧
单调队列及其应用
单调队列,望文生义,就是指队列中的元素是单调的。如:{a1,a2,a3,a4……an}满足a1<=a2<=a3……<=an,a序列便是单调递增序列。同理递减队列也是存在的。
单调队列的出现可以简化问题,队首元素便是最大(小)值,这样,选取最大(小)值的复杂度便为O(1),由于队列的性质,每个元素入队一次,出队一次,维护队列的复杂度均摊下来便是O(1)。
如何维护单调队列呢,以单调递增序列为例:
1、如果队列的长度一定,先判断队首元素是否在
规定
关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定
范围内,如果超范围则增长队首。
2、每次加入元素时和队尾比较,如果当前元素小于队尾且队列非空,则减小尾指针,队尾元素依次出队,直到满足队列的调性为止
要特别注意头指针和尾指针的应用。
下面介绍单调队列的具体应用:
一、单调队列的直接应用
1.合并果子
【问题描述】
在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过n-1次合并之后,就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1,并且已知果子的种类数和每种果子的数目,你的任务是
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
出合并的次序
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
,使多多耗费的体力最少,并输出这个最小的体力耗费值。
例如有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。
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
:
这个题目非常的经典,发放也很多,可以采用快排或者堆,其思想都是选取当前最小的两个堆进行合并。复杂度均为O(nlOgn),如果用有序队列维护,时间复杂度为O(n)。
每次选取进行合并的两堆,不是最先给定的堆,就是合并最初堆若干次后得到的新堆,所以需要维护两个单调递增队列,一个队列存最初给定的堆的值(1),一个存合并后得到的新值(2)。
每次选择时有三种状态:
1.选取队一的队首两个
2.选取队2的的队首两个
- 1 –2011-08-09
3.选取二者队首各一个
只需对每个队列的指针做相应的更改。
特别注意初始化。
这道题很好的运用了题目中决策的单调性,对初始对经行排序,保证了其单调性。而对于新产生的堆来说,一旦有新元素加入其中,则新元素一定大于原有元素。(很显然,由于队列1的单调性)。
也就是说,队列的单调性是自然而然的。是不需要维护的。要善于观察分析,才能发现。
【程序代码】
prOgram because_Of_lOve;
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
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>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”,表示面试开始
接下来的数据中有三种情况:
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
END
START
Q
C ccQ 200
C cxw 100
Q
G
Q
C wzc 500
Q
END
Sample Output
1000000000
-1
200
100
分析:
题目本身就是队列,由于要找的是最大值,我们自然想到用单调队列解决问题。
维护一个单调递减序列,只需输出序列中的第一个元素即可。
对于命令我们可以进行不同的处理:
如果是Q命令,则判断当前队列中是否仍有元素,如果没有则输出-1,如果有则直接输出队首。
中的位置>=last)
如果是C命令,则将该元素加入队列中,并和队尾元素比较,维护队列的单调性。
这里考虑一个问题,当前元素加如后对队尾元素为什么可以毫无保留的删去呢?
因为当前加入的元素比队尾元素大,且该元素比队尾元素入队晚(也就是该元素比队尾元素晚出队),所以只要该元素在队列中,就一定不会选取队尾元素。也就是当前状态一定比队尾元素的状态更优。——这里一定要理解深刻,这是队列的本质。
因此,这题的单调队列中维护的一个属性是元素的价值,一个属性是单调队列中的元素在原序列中的位置。
注意,q中的值是该元素在原序列中的位置!
【程序代码】
prOgram because_Of_lOve;
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;
while s<>'END' dO
begin
readln(s);
case s[1] Of
'G':begin
inc(last);
while (q[l]<=last)and(l<=r)dO inc(l);
end;
'Q':begin
if l>r then writeln(-1)
else writeln(a[q[l]]);
end;
'C':begin
inc(tt);
delete(s,1,2);
w:=pOs(' ',s);
delete(s,1,w);
val(s,a[tt]);
while(a[tt]>a[q[r]])and(l<=r)dO dec(r);
inc(r);
q[r]:=tt;
end;
end;
end;
end.
4、广告印刷
【问题描述】
最近,afy决定给TOJ印刷广告,广告牌是刷在城市的建筑物上的,城市里有紧靠着的N个建筑。afy 决定在上面找一块尽可能大的矩形放置广告牌。我们假设每个建筑物都有一个高度,从左到右给出每个建筑物的高度H1,H2…HN,且0ans then ans:=(right[i]-left[i]-1)*h[i]; writeln(ans);
end.
5、总结
单调队列的应用仍有很多实例,这一不能一一道出。
首先考虑问题需要的时间复杂度如果是O(n)的算法,单调队列是首选。
其次要善于观察分析,发现题目中的单调性。决策的单调(合并果子),要求问题的特性(windOw),元素价值和其在原序列中位置的单调(志愿者),问题结果的单调(广告印刷)。
二、单调队列在优化动态规划中的应用
做动态规划时常常会见到形如这样的转移方程:
f[x] = max Or min{g(k) | b[x] <= k < x} + w[x]
(其中b[x]随x单调不降,即b[1]<=b[2]<=b[3]<=...<=b[n])
(g[k]表示一个和k或f[k]有关的函数,w[x]表示一个和x有关的函数)
这个方程怎样求解呢?我们注意到这样一个性质:如果存在两个数j, k,使得j <= k,而且g(k) <= g(j),则决策j是毫无用处的。因为根据b[x]单调的特性,如果j可以作为合法决策,那么k一定可以作为合法决策,又因为k比j要优,(注意:在这个经典模型中,“优”是绝对的,是与当前正在计算的状态无关的),所以说,如果把待决策表中的决策按照k排序的话,则g(k)必然是不降的。
这样,就引导我们使用一个单调队列来维护决策表。对于每一个状态f(x)来说,计算过程分为以下几步:
1、队首元素出队,直到队首元素在给定的范围中。
2、此时,队首元素就是状态f(x)的最优决策,
3、计算g(x),并将其插入到单调队列的尾部,同时维持队列的单调性(不断地出队,直到队列单调为止)。
重复上述步骤直到所有的函数值均被计算出来。不难看出这样的算法均摊时间复杂度是O(1)的。因此求解f(x)的时间复杂度从O(n^2)降到了O(n)。
单调队列指一个队列中的所有的数符合单调性(单调增或单调减),在信息学竞赛的一些题目上应用,会减少时间复杂度
单调队列的每个元素一般会存储两个值:
1.在原数列中的位置(下标)
单调队列同时保证这两个值单调。
下面看几个优化的实例:
1、烽火传递
描述DescriptiOn
(烽火传递)烽火台又称烽燧,是重要的防御设施,一般建在险要处或交通要道上。一旦有敌情发生,白天燃烧柴草,通过浓烟表达信息:夜晚燃烧干柴,以火光传递军情。在某两座城市之间有n个烽火台,每个烽火台发出信号都有一定的代价。为了使情报准确的传递,在m个烽火台中至少要有一个发出信号。现输入n,m和每个烽火台发出的信号的代价,请计算总共最少需要话费多少代价,才能使敌军来袭之时,情报能在这两座城市之间准确的传递。
例如,有5个烽火台,它们发出信号的代价为1,2,5,6,2,且m为3,则总共最少花费的代价为4,即由第2个和第5个烽火台发出信号。
输入格式Input FOrmat
第一行有两个数n,m分别表示n个烽火台,在m个烽火台中至少要有一个发出信号。
第二行为n个数,表示每一个烽火台的代价。
输出格式Output FOrmat
一个数,即最小代价。
样例
5 3
1 2 5 6 2
4
时间限制Time LimitatiOn
各个测试点1s
注释Hint
1<=n,m<=1,000,000
分析
我们想到了用单调队列进行优化,由于随着i的循环,每次只有一个i进入决策区间也只有一个i出决策区间,由于每次选取决策区间中的最小值,所以维护一个单调递增序列,每次取出队首元素即可。
为什么可以将队尾元素无情的删去呢?由于后进队的序列同时满足在原序列中的位置更靠后和其在动态规划中的价值更大。这样选取这个元素就要比选取之前的任何一个决策要优,所以之前被删掉的决策都是无用的。
这道题的本质就是用单调队列维护了决策本身的价值和其在原序列中位置的同时单调。
要特别注意单调队列中的值是决策在原决策序列中的位置。
【程序代码】
prOgram because_Of_lOve;
var
a,f,q:array[0..1000000] Of lOngint;
m,n,l,r,i,ans:lOngint;
begin
readln(n,m);
fOr i:=1 tO n dO
read(a[i]);
f[0]:=0;
l:=1;r:=0;
fOr i:=1 tO n dO
begin
while(q[l]f[i] then ans:=f[i];
writeln(ans);
end.
2、难题的解决
给定一个序列,读入n,k和a1~an,让你求出该序列中包含第k项的最长上升子序列长度。
1<=n<=300000 k<=n
分析
不要被问题的表面现象迷惑,既然要包含第k项,那么在k项的左边,比第k项大
的元素一定不会进入目标序列。同理在k项的右边,比第k项小的元素一定也不会进入目标队列。
那么我们直接把这些无用的元素删去。
剩下的队列就好看得多。在k项之前的元素都比k小,之后的都比k项大。我们只需从1~k-1求一遍最长上升子序列,再从k+1~n求一遍最长上升子序列即可。最后结果为二者的值加1。
由于数据范围很大,用传统的n2算法无法完成任务。所以本题地关键是(nlOgn)的lis
假如x
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
这个值,即d[k]:=min{a[t]}(f[t]=k)
我们注意到d有两个特点:
1. d[k]的值在整个过程中是单调不上升的。
2. d数组是有序的。即d1d[len]将其直接假如d,inc(len)得到更长的序列
否则,在d中查找到第一个比该元素小的元素d[k],将该元素加入,d[k+1]:=x;如果使用
顺序查找效率会很低,所以采用二分查找,将其复杂度降为lOg级,难点在于二分查找。
本题中的单调队列的出现时利用决策的性质,用元素在动归中的价值分类。在入队操做
时并未让所有元素出队,而是直接插入相应位置,这是根据题目的特殊性决定的。对于一个单调的序列往往用二分法。
当然这种发法也可推广到其他的最XX序列问题
上面说的已经很详细,代码就省了。
三、一些总结
单调队列有很多的应用,这里只是介绍了一部分,特别是在优化动态规划时。
希望读者能在实践中形成自己的方法
- 16 –2011-08-09
浙公网安备 33021202002483