|
|
8#
楼主 |
发表于 2018-8-27 09:21:32
|
只看该作者
单调队列顾名思义就是一个有规律的队列，这个队列的规律是：所有在队列里的数都必须按递增（或递减）的顺序列队，如果真有这么一个队列，那么队列的头是不是就是最小（或最大）的呢？
看看顶楼的那个题目，我们朴素的想法就是解法1：按照常规方法，我们在求fi即i~i+m-1区间内的最值时，要把区间内的所有数都访问一遍，时间复杂度约为O（nm）。有没有一个快一点的算法呢？
解法2：我们知道，上一种算法有一个地方是重复比较了，就是在找当前的f(i)的时候，i的前面k-1个数其它在算f(i-1)的时候我们就比较过了。那么我们能不能保存上一次的结果呢？当然主要是i的前k-1个数中的最大值了。这就要用到单调递减队列。
使用单调队列就涉及到去头和删尾：
1、队列的头一定是在一段时间前就加入了队列，现在的队列头会不会离开了我们处理的区间呢？如果它离我们正在处理的i太远了，我们就要把它去掉，去除冗杂的信息。
2、为了保证队列的递减性，在从列队尾新插入元素v时，要考虑队列尾的值是否大于v，如果是，队列呈现 队列尾-1的值 > 队列尾的值 > v ，此时队列递减性没有消失；如果不是，队列呈现 队列尾-1的值 > 队列尾的值 < v ，队列递减性被打破。
为了维护递减性，我们做如下考虑：v是最新值，它的位置是目前最靠后的，它可成为以后的最大值，必须留下；队列尾-1的值与v大小不定，不能冒然删去它；队列尾的值夹在v和队列尾-1之间，它不但不是最大值，对于以后的情况又不如v优，因为v相比队列尾更靠后（v可以影响到后m个值，队列尾只能影响到从它的位置往后数m-1个值），而且值更大，所以删队列尾是必定的。
在维护好一个 区间正确、严格递减 的单调递减队列后，队列头就是当前区间的最大值了。
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
-
- int a[200000];
- struct node
- {
- int x,p;
- node(){}
- node(int xx,int pp){x=xx;p=pp;}
- }list[200000];
-
- int main()
- {
- int n,m;
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++) scanf("%d",&a[i]);
- int head=1,tail=1;
- list[1]=node(a[1],1);
- for(int i=2;i<=n;i++)
- {
- while(head<=tail&&list[tail].x<=a[i]) tail--;//删尾
- list[++tail]=node(a[i],i);//得到最优解并插入
- while(i-list[head].p>=m) head++;//去头
- if(i>=m) printf("%d\n",list[head]);
- }
- return 0;
- }
整理归纳单调队列的定义：
1、维护区间最值；
2、去除冗杂状态；
3、保持队列单调（最大值是单调递减序列，最小值是单调递增序列）；
4、最优选择在队首。
整理归纳单调队列的使用方法：
1、维护队首（对于上题就是如果你已经是当前的m个之前那你就可以被删了） ；
2、在队尾插入（每插入一个就要从队尾开始往前去除冗杂状态） ；
3、取出需要的最优解（队列头的值即是）；
4、借助最优解，得到目前所求的最优解（通常此处插入DP方程）。
单调队列的原理：
在处理fi时，去除冗杂、多余的状态，使得每个状态在队列中只会出现一次；同时维护一个能瞬间得出最优解的队列，减少重新访问的时间；在取得自己所需的值后，为后续的求解做好准备。 |
|
发表于 2018-5-13 00:43:08
收藏
