华师一附中OI组

标题: 单调队列练习题 [打印本页]

作者: admin 时间: 2018-5-13 00:43
标题: 单调队列练习题
题目描述
【题意】
给定一个n个数的数列，从左至右输出每个长度为m的数列段内的最大数。
比如8个数的数列[1 3 -1 -3 5 3 6 7],m=3，那么每连续3个最大值如下：

位置	最大值
[1 3 -1] -3 5 3 6 7	3
1 [3 -1 -3] 5 3 6 7	3
1 3 [-1 -3 5] 3 6 7	5
1 3 -1 [-3 5 3] 6 7	5
1 3 -1 -3 [5 3 6] 7	6
1 3 -1 -3 5 [3 6 7]	7

【输入格式】
第一行两个整数n和m( 1<= n <= 20 0000,m<=n）。
下来给出n个整数。
【输出格式】
一行一个整数，表示每连续m个数的最大值。
【样例输入】
8 3
1 3 -1 -3 5 3 6 7
【样例输出】
3
3
5
5
6
7

作者: admin 时间: 2018-5-13 00:43
题目描述
【题意】
有N个数(N<=100000)，在连续M（M<=N）个数里至少要有一个数被选择。
求选出来数的最小总和。
【输入格式】
第一行两个整数 N，M
接下来N行 ai（ai<=100）表示第i个数
【输出格式】
一个整数，最小总和
【样例输入】
5 3
1
2
5
6
2
【样例输出】
4

作者: admin 时间: 2018-5-13 00:46
题目描述
【题意】
一个数列有N(1 <= N <= 100,000)个数(0<=ai<=10^9)。
开始选数，要求选出来的数和最大。
限制：不能选中超过连续M（M<=N）个。
【输入格式】
第一行两个整数N和M;
下来给出n个数。
【输出格式】
一行一个整数，表示可以得到的最大的和。
【样例输入】
5 2
1
2
3
4
5
【样例输出】
12

作者: admin 时间: 2018-5-13 00:46
题目描述
【题意】
一个猴子要吃香蕉，一共N棵香蕉树排列在一条直线上，它一开始在第一棵树上。
每棵树上有不同数量的香蕉，猴子每次最多的跳跃距离为D，而且最多只能跳M次，问猴子最多能吃到多少香蕉？
【输入格式】
第一行三个整数 N,D,M (M<N<=5000，D<=10000)
下面N行每行两个整数 ai,bi (ai,bi<=1000000) 分别表示每棵树上的香蕉数目，以及每棵树的位置(树的位置是递增的）
数据保证没有两棵香蕉树在同一位置，以及b1=0
【输出格式】
一个整数，表示猴子最多吃到的香蕉数。
【样例输入】
5 5 2
6 0
8 3
4 5
6 7
9 10
【样例输出】
20

作者: admin 时间: 2018-5-13 00:46
题目描述
【题意】
给一个N*M的数矩阵
现在求一个子矩阵要求子矩阵中最大值与最小值的差<=C。而且子矩阵的宽度(横）不超过100（长（竖）没有限制）。求子矩阵的最大面积。
【输入格式】
第一行两个整数 M（左右方向），N（上下方向）和 C (N,M<=500 0<=C<= 10 )
接下来 N行每行M个数每个数(-30000~30000)
【输出格式】
子矩阵的最大面积
【样例输入】
10 15 4
41 40 41 38 39 39 40 42 40 40
39 40 43 40 36 37 35 39 42 42
44 41 39 40 38 40 41 38 35 37
38 38 33 39 36 37 32 36 38 40
39 40 39 39 39 40 40 41 43 41
39 40 41 38 39 38 39 39 39 42
36 39 39 39 39 40 39 41 40 41
31 37 36 41 41 40 39 41 40 40
40 40 40 42 41 40 39 39 39 39
42 40 44 40 38 40 39 39 37 41
41 41 40 39 39 40 41 40 39 40
47 45 49 43 43 41 41 40 39 42
42 41 41 39 40 39 42 40 42 42
41 44 49 43 46 41 42 41 42 42
45 40 42 42 46 42 44 40 42 41
【样例输出】
35

作者: admin 时间: 2018-5-13 00:47
练习：

POJ2823

POJ1156

HDU3041

POJ3017

作者: admin 时间: 2018-5-13 19:52
http://www.hsyit.cn/forum.php?mod=viewthread&tid=35966

作者: admin 时间: 2018-8-27 09:21
单调队列顾名思义就是一个有规律的队列，这个队列的规律是：所有在队列里的数都必须按递增（或递减）的顺序列队，如果真有这么一个队列，那么队列的头是不是就是最小（或最大）的呢？
看看顶楼的那个题目，我们朴素的想法就是解法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时，去除冗杂、多余的状态，使得每个状态在队列中只会出现一次；同时维护一个能瞬间得出最优解的队列，减少重新访问的时间；在取得自己所需的值后，为后续的求解做好准备。

欢迎光临华师一附中OI组 (http://hsyit.cn/)