洛谷1440 求m区间的最小值 单调队列

题目描述

一个含有n项的数列(n<=2000000)，求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始，若前面没有数则输出0。

输入格式：

第一行两个数n，m。

第二行，n个正整数，为所给定的数列。

输出格式：

n行，第i行的一个数ai，为所求序列中第i个数前m个数的最小值。

输入样例#1：

6 2

7 8 1 4 3 2
输出样例#1：

0

7

7

1

1

3

单调队列模板题 
用一个队列维护第i个数前m个最小值的位置
注意在判断的时候要保持队列非空，否则会导致在队列为空的时候队首提前

#include<bits/stdc++.h>

using namespace std;

#define maxn 2000005

int a[maxn],q[maxn];

int n,m,l=,r;

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++){

        scanf("%d",&a[i]);

    }

    for(int i=;i<=n;i++){

        printf("%d\n",a[q[l]]);

        if(i-q[l]+>m&&l<=r)l++;

        while(a[i]<a[q[r]]&&l<=r)r--;

        q[++r]=i;

    }

    return ;

}

//Luogu1440

//拿STLdeque写了会TLE一个点还要挂快速读入才能A

#include<bits/stdc++.h>

using namespace std;

int read(){

    int x=,t=;char c;c=getchar();

    while(c<''||c>''){if(c=='-')t=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*t;

}

int N,M,a[];

deque <int> q;

int main()

{

    N=read(),M=read();

    for(int i=;i<=N;i++){

        if(q.empty())printf("0\n");

        else printf("%d\n",a[q.front()]);

        a[i]=read();

        if(i-q.front()+>M&&!q.empty())q.pop_front();

        while(!q.empty()&&a[q.back()]>a[i])q.pop_back();

         q.push_back(i);

    }

    return ;

} 

STL代码 该回答已被折叠