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

题目传送门

题目描述

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

输入格式

第一行两个整数，分别表示 n，m。

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

输出格式

n 行，每行一个整数，第 i 个数为序列中 $a_i$ 之前 m 个数的最小值。

解题思路：

这道题与滑动窗口的题比较起来不能说一模一样，只能说完全一致。差不多看到标题就知道可以用单调队列来解。当然注意这里用cin会超时。这道题要强调的是每次输出结果是不把本次输入的数字算在内的，因此，我们只需要对单调队列的操作和输出结果的位置调换一下即可。

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define INF 0x3f3f3f3f

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    deque<pair<int,int> > q;
    for(int i = 1;i <= n;i++){
        int num;
        scanf("%d",&num);
        printf("%d\n",(q.size() ? q.front().first : 0));//输出结果
        while(q.size() && q.back().first >= num) q.pop_back();//维护单调性
        while(q.size() && i - q.front().second >= m) q.pop_front();//清除过期元素
        q.push_back(make_pair(num,i));//入队
    }

    return 0;
}