【题解】P1440 求m区间内的最小值

0
9

求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;
}

<

发布回复

请输入评论!
请输入你的名字