【题解】P1440 求m区间内的最小值
2019-12-23 16:00:28来源:博客园 阅读 ()
【题解】P1440 求m区间内的最小值
求m区间内的最小值
题目描述:
一个含有n项的数列(n<=2000000),求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始,若前面没有数则输出0。
分析:
读题之后可以发现,这道题就是在求:
给出一个长度为n的序列A,求A中所有长度为m的连续子序列中的最小值
而针对这种问题,单调队列似乎是我们最好的选择。
单调队列,说是队列,却不符合队列“先进先出”的原则,它只是沿用了队列的思想,并具有一定的单调性,拥有一个队列头head和一个队列尾tail,用head和tail来控制队列的长度,筛选队列中的元素以及保持队列的单调性。
但怎样控制队列的长度,筛选队列中的元素以及保持队列的单调性呢?
这就是单调队列的实现了。
用样例来分析一下:
6 2
7 8 1 4 3 2
这样,我们就拥有了一个初始队列:7 8 1 4 3 2
拥有上帝视角的我们可以看出答案是:
0
7
7
1
1
3
这时候,我们发现,不论第一个元素是多少,它之前m个元素的最小值永远为0(因为它之前并没有元素)?,而最后一个元素是多少也没有关系(因为它之后并没有元素)。
所以我们只用找到第2个到第n个元素中每个前m个元素的最小值就可以了,那么单调队列的单调性也应该是递增的,我们就可以把队列里每个元素的序号放入单调队列操作,就可以得到答案了。
于是我们可以开始模拟了:
考虑第一个元素,i=1,head=1,tail=0,q[tail]=0,a[1]=7,a[1]>a[ q[tail] ],把a[1]放入不会破坏单调性,q[head]=0,这个元素距队首元素的距离为0,则队列为:1
考虑第二个元素,i=2,head=1,tail=1,q[tail]=1,a[2]=8,a[2]>a[ q[tail] ],把a[2]放入不会破坏单调性,q[head]=1,这个元素距队首元素的距离为1,则队列为:1 2
考虑第三个元素,i=3,head=1,tail=2,q[tail]=2,a[3]=1,但a[3]<a[ q[tail] ],把a[3]放入会破坏单调性,而a[3]<a[ q[tail] ],由于求最小值,所以只能将a[ q[tail=2] ]弹出队列来保证单调性了,而a[3]>a[ q[tail=1] ],这时再将a[3]放入就不会破坏单调性了,q[head]=1,这个元素距队首元素的距离为2,达到长度m=2了,这队列头head就向后移,则队列为:3。
以此类推,直到第n-1个,因为第n个后面没有元素,所以第n个不会进入队列,每次都输出队列头对应的元素值,就得到了答案。
代码实现:
#include <iostream>
#include <cstdio>
#include <cmath>
#define maxn 2000005
using namespace std;
int n,m;
int a[maxn];
int q[maxn];
int head,tail;
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
head=1;
tail=0;
printf("0\n");//第一个元素它之前并没有元素
for(int i=1;i<n;i++)//从1~n-1个,第n个不进队列
{
while((head<=tail)&&((i-q[head])>=m)) head++;//控制队列的长度
while((head<=tail)&&(a[q[tail]]>=a[i])) tail--;//筛选队列中的元素
tail++;
q[tail]=i;//保持队列的单调性
printf("%d\n",a[q[head]]);//输出答案
}
return 0;
}
原文链接:https://www.cnblogs.com/Von-ZH/p/12085356.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Unsolved --> Solved OJ思路题解 2020-05-30
- 【题解】Luogu1739 表达式括号匹配 2020-04-07
- 【题解】Building Strings Gym - 102152E 2020-03-31
- GPLT-天梯赛-题解目录 2020-03-22
- 题解 P5116 【[USACO18DEC]Mixing Milk】 2020-03-14
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash