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

· · 题解

吐槽

感觉其他题解没有写清楚，本蒟蒻愣是搞了一下午的单调队列，一脸懵逼。

于是打算写一个详细一点的题解，也可以加深一下自己的印象。ps：第一次写题解，写得不好不要介意。

思路

其实题目意思可看成求1—n-1的每一项的前m项中的最小值

首先构造一个单调增的队列，每次进来一个数的时候，与队尾的数比较；如果比队尾的数小，那么这个数直接入队，如果比队尾数大，r--，弹出队尾，然后继续比下去直到比队尾数大或队列为空为止。当长度超过m时，l++，把队首弹掉。这样，只需每次输出队首，就是当前的最小值。

那么怎么判断当前的长度呢？我们注意到，由于新的数总是从后往前插入，于是队列中各个数的序号也是单调增的。也就是说，队首一定是最先进来的，所以只需用队首的序号减去当前的数的序号再+1就行。

举个例子

2 4 6 8 3 5 4 2（m=4） （先输出一个0）

操作 队列 当前区域 输出
2入队 2 2 2
4入队 2 4 2 4 2
6入队 2 4 6 2 4 6 2
8入队 2 4 6 8 2 4 6 8 2
6、4、2出队，3入队 3 4 6 8 3 3
5入队 3 5 6 8 3 5 3
5出队，4入队 3 4 8 3 5 4 3

只需算到n-1

代码

由于各元素序号也必须存储，才能判断长度，所以这里我的队列里面存的是元素序号

#include<cstdio>
int q[2000001],n,m,l=1,r=1,x,a[2000001];
int main()
{
    scanf("%d%d",&n,&m);
    printf("0\n");
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d",&a[i]);
        while(a[q[r-1]]>=a[i]&&l<r)r--;
        //r是队尾，是空节点，r-1才是队列最后一个数 
        q[r++]=i;
        if(i-q[l]+1>m)l++;//如果长度大于m 
        printf("%d",a[q[l]]);
        if(i!=n-1)printf("\n");
    }
    return 0;
}