当前位置:首页 >> 学科竞赛 >>

单调队列的应用


COCI 2009 Ograda_题目
(烽火传递)烽火台又称烽燧 单调队列及其应用 单调队列, 望文生义, 就是指队列中的元素是单调的。 {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 129 【样例输出】 15 【数据规模】 对于 30%的数据,保证有 n <= 1000; 对于 50%的数据,保证有 n <= 5000; 对于全部的数据,保证有 n <= 10000。 分析: 这个题目非常的经典,发放也很多,可以采用快排或者堆,其思想都是选取当前最小的两个堆进行合并。复 杂度均为 O(nlOgn),如果用有序队列维护,时间复杂度为 O(n)。 每次选取进行合并的两堆,不是最先给定的堆,就是合并最初堆若干次后得到的新堆,所以需要维护两个单 调递增队列,一个队列存最初给定的堆的值(1),一个存合并后得到的新值(2)。 每次选择时有三种状态: 1.选取队一的队首两个 2.选取队 2 的的队首两个

- 1 –

2011-08-09

COCI 2009 Ograda_题目
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<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);

- 2 –

2011-08-09

COCI 2009 Ograda_题目
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

- 3 –

2011-08-09

COCI 2009 Ograda_题目
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) 世博会马上就要开幕了,福州大学组织了一次志愿者选拔活动。 参加志愿者选拔的同学们排队接受面试官们的面试。 参加面试的同学们按照先来先面试并且先结束的原则接 受面试官们的考查。

- 4 –

2011-08-09

COCI 2009 Ograda_题目
面试中每个人的人品是主要考查对象之一。(提高人品的方法有扶老奶奶过街,不闯红灯等) 作为主面试官的 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 Q

- 5 –

2011-08-09

COCI 2009 Ograda_题目
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,之后对于队列中所有超出范围的前端元素进行出队操作。(该元素在原序列

- 6 –

2011-08-09

COCI 2009 Ograda_题目
中的位置>=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; last:=0;

- 7 –

2011-08-09

COCI 2009 Ograda_题目
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;

- 8 –

2011-08-09

COCI 2009 Ograda_题目
end; end.

4、广告印刷 【问题描述】 最近,afy 决定给 TOJ 印刷广告,广告牌是刷在城市的建筑物上的,城市里有紧靠着的 N 个建筑。afy 决定在上面找一块尽可能大的矩形放置广告牌。 我们假设每个建筑物都有一个高度, 从左到右给出每个建筑物的 高度 H1,H2…HN,且 0<Hi<=1,000,000,000,并且我们假设每个建筑物的宽度均为 1。要求输出广告牌的 最大面积。 【输入文件】 中的第一行是一个数 n (n<= 400,000 ) 第二行是 n 个数,分别表示每个建筑物高度 H1,H2…HN,且 0<Hi<=1,000,000,000。 【输出文件】 输出文件 ad.Out 中一共有一行,表示广告牌的最大面积。 【输入样例】 6 584484 【输出样例】 24

【分析】 最终的广告牌一定等于某个建筑物的高度×其能达到的最大长度 现在,建筑物的高度已知,现在只需要知道每个高度能达到的最大长度是多少。由于 n 是 400000,我们 只能用 O(n)或 O(nlOgn)的算法。可以使用 rmq,在后边的论文中会讲到。 现在讲时间复杂度为 O(n)的单调队列的方法。 继续上边的思路,对于每个建筑物,只需要找到其能够扩展到的最大宽度即可。也就是这个建筑物的左右两 边的比它低或等于它的建筑物个数。

- 9 –

2011-08-09

COCI 2009 Ograda_题目
如何用单调队列呢? 我们从 1~n 一次进队,维护一个单调递减序列。每次加入元素后维护其单调性,当然这样做必然会使一些 元素出队, 出队的元素一定要比当前加入的元素小, 也就是说当前元素就是出队的元素能在右侧达到的最远的建 筑物! 注意, 要让 h[n+1]=0 并且让该元素入队一次(会使当前队列中的所有元素出队), 保证每个元素都有其 “右 极限”的值。 要求“左极限”同理,只需从 n~0 循环即可,注意 0 这道题是对单调队列的变形使用。由于问题的结果具有单调性,很好的利用出队元素的特性。

【程序代码】 prOgram because_Of_lOve; var q:array[0..40000] Of lOngint; n,i,l,r,ans:lOngint; h,left,right:array[0..40000] Of lOngint;

begin readln(n); fOr i:=1 tO n dO read(h[i]); l:=1; r:=0; fOr i:=1 tO n+1 dO begin while (h[i]<h[q[r]])and(l<=r) dO

- 10 –

2011-08-09

COCI 2009 Ograda_题目
begin right[q[r]]:=i; dec(r); end; inc(r); q[r]:=i; end; l:=1; r:=0; fOr i:=n dOwntO 0 dO begin while (h[i]<h[q[r]])and(l<=r)dO begin left[q[r]]:=i; dec(r); end; inc(r); q[r]:=i; end; fOr i:=1 tO n dO if (right[i]-left[i]-1)*h[i]>ans then ans:=(right[i]-left[i]-1)*h[i]; writeln(ans); end.

- 11 –

2011-08-09

COCI 2009 Ograda_题目
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.在原数列中的位置(下标) 2.该元素在动态规划中的状态值(价值)

- 12 –

2011-08-09

COCI 2009 Ograda_题目
单调队列同时保证这两个值单调。 下面看几个优化的实例: 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 一个数,即最小代价。 样例 53 12562

4 时间限制 Time LimitatiOn 各个测试点 1s 注释 Hint 1<=n,m<=1,000,000 分析 要用动态规划的方法解决。我们可以写出这样的方程 f[i]:=min{f[j]}+a[i](i-m<=j<i-1)(因为要保证 i 之前的 3 个中必须存在被点亮的烽火台)。单纯这样循环会造成超时。

- 13 –

2011-08-09

COCI 2009 Ograda_题目
我们想到了用单调队列进行优化,由于随着 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]<i-m)and(l<=r)dO inc(l); while(f[i-1]<f[q[r]])and(l<=r)dO dec(r); inc(r); q[r]:=i-1; f[i]:=f[q[l]]+a[i]; end;

- 14 –

2011-08-09

COCI 2009 Ograda_题目
ans:=maxlOngint; fOr i:=n dOwntO n-m+1 dO if ans>f[i] then ans:=f[i]; writeln(ans); end.

2、难题的解决 给定一个序列,读入 n,k 和 a1~an,让你求出该序列中包含第 k 项的最长上升子序列长度。 1<=n<=300000 分析 不要被问题的表面现象迷惑,既然要包含第 k 项,那么在 k 项的左边,比第 k 项大 的元素一定不会进入目标序列。同理在 k 项的右边,比第 k 项小的元素一定也不会进入目标队列。 那么我们直接把这些无用的元素删去。 剩下的队列就好看得多。在 k 项之前的元素都比 k 小,之后的都比 k 项大。我们只需从 1~k-1 求一遍最长 上升子序列,再从 k+1~n 求一遍最长上升子序列即可。最后结果为二者的值加 1。 由于数据范围很大,用传统的 n2 算法无法完成任务。所以本题地关键是(nlOgn)的 lis 假如 x<y<t 且 a[x]<a[y],f[x]=f[y],也就是说选取 x,y 都可以更新得到相同的的 f[t]的值,那么选取谁 呢。显然选取 x 会更优,因为在 a[x]…a[y]中如果存在 a[z],使得 a[x]<a[z]<a[y]那么就可以通过 x 得到更 长的最长不降子序列的值。 根据 f 的值进行分类,我们只需要保留满足 f[t]=k 的所有 a[t]中的最小值,设 d[k]记录这个值,即 d[k]:=min{a[t]}(f[t]=k) 我们注意到 d 有两个特点: 1. 2. d[k]的值在整个过程中是单调不上升的。 d 数组是有序的。即 d1<d2<….<dn k<=n

利用 d,我们可以得到一种计算最长上升子序列的方法。设当前已经求出的最长上升序 列的长度为 len,每次读入一个新元素 x。

- 15 –

2011-08-09

COCI 2009 Ograda_题目
如果 x>d[len]将其直接假如 d,inc(len)得到更长的序列 否则,在 d 中查找到第一个比该元素小的元素 d[k],将该元素加入,d[k+1]:=x;如果使用 顺序查找效率会很低,所以采用二分查找,将其复杂度降为 lOg 级,难点在于二分查找。 本题中的单调队列的出现时利用决策的性质,用元素在动归中的价值分类。在入队操做 时并未让所有元素出队,而是直接插入相应位置,这是根据题目的特殊性决定的。对于一个单调的序列往往 用二分法。 当然这种发法也可推广到其他的最 XX 序列问题 上面说的已经很详细,代码就省了。

三、一些总结 单调队列有很多的应用,这里只是介绍了一部分,特别是在优化动态规划时。 希望读者能在实践中形成自己的方法

- 16 –

2011-08-09



相关文章:
浅谈DP优化之单调队列优化
浅谈DP优化之单调队列优化_计算机软件及应用_IT/计算机_专业资料。浅谈 DP 优化之单调队列优化先来看一道简单题 EOJ469 Mowing the Lawn FJ 有 N (1 <= N ...
单调队列题目汇总
单调队列的具体作用在于,由于保持队列中的元素满足单调性, 对于上述问题中的每个...单调队列 2页 1下载券 初谈单调队列 3页 1下载券 单调队列的应用 16页 免费...
单调队列作业
(john.out) 样例输入:14 4 样例输出: 4 8 12 2 7 13 5 11 6 1 14 3 10 9 单调队列作业 1、Sliding window1 给你一个长度为 N 的数组,一个长为...
单调队列题目
求出 f[i]后,将决策 i 插入单调队列中,维护单调性,从队尾 插入,若 h[r...单调队列的应用 16页 免费 单调队列 36页 1下载券 栈与队列相关题目 14页 免费...
浅谈DP优化之单调队列优化
END FOR 8. END FOR 已知单调队列的效率是 O(n),那么加上单调队列优化以后...单调队列的应用 16页 免费 关于dp的斜率优化 6页 免费 树形dp与优化方法 14页...
用单调性优化动态规划
本文主要选取了几道国内竞赛试 题,探讨单调性在动态规划优化中神奇的应用。 【关键字】 单调性 动态规划 队列 凸线 -1- JSOI2009 集训队论文 【目录】 【序言...
初二数学期末复习《一次函数的应用—动点问题》(附练习...
初二数学期末复习《一次函数的应用—动点问题》(附练习及答案) - 课 题 一次函数的应用——动点问题 1.学会结合几何图形的性质,在平面直角坐标系中列函数关系式...
聚苯乙烯的应用及研究发展方向
《高分子材料基础》课程论文 聚苯乙烯的应用及研究发展方向摘要:自从 20 世纪 30 年代初期聚苯乙烯第一次在德国实现了工业生产以后, 它的应用领域也在不断扩大,...
GHOST 的详细功能及应用!
GHOST 的详细功能及应用!_信息与通信_工程科技_专业资料。电脑 GHOST GHOST 的详细功能及应用 我们能用 Ghost 做什么?●可以创建硬盘镜像备份文件 ●可以将备份...
bzoj刷题总结列表_计算机软件及应用_IT/计算机_专业资料
bzoj刷题总结列表_计算机软件及应用_IT/计算机_专业资料。大多是水题。。...每次同时拓展所有点,ans=拓展次数 1047: [HAOI2007]理想的正方形 dp,单调队列...
更多相关标签: