007. 求m区间内的最小值（洛谷P1440）

题目描述

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

6 2
7 8 1 4 3 2

样例输出 #1

0
7
7
1
1
3

提示

对于 \(100\%\) 的数据，保证 \(1\le m\le n\le2\times10^6\)，\(1\le a_i\le3\times10^7\)。

题解

单调队列嘛，就是单调的队列
单调递增或者单调递减
所以说答案（也就是最优解）就存在队首，而队尾则是最后进队的元素
那么怎么判断这个数是否还在这个区间之内呢？
这时候就要用到一个结构体了

struct node
{
    int val;
    int pos;
};

val存储该点的值，pos存储该点的位置，就是为了能够在循环中判断能否把这个点踢掉
根据单调队列的性质，如果我们想要将一个新的点插入
（你比如）
先看样例 当我们要在队列中插入第m + 1个元素的时候
也就是1
现在队列中是 7 8
他们分别对应的位置 1 2
因为要从队尾插入嘛
你想想你排队 如果有人一下子直接到队首，你是不是会很不爽，认为他没有资格
但是如果他一个一个插队，从队尾挨个上来，你不爽也没用的
所以单调队列也是队列，也是如此，没有元素有资格直接到头
你要慢慢来
这时候代码就很明显了

while((head <= tail)&&(v[tail].val >= a[i - 1]))
            tail--;
        v[++tail].val = a[i - 1];
   //这里i - 1要解释一下，因为该题0也要计算进去

那么对于已经过期的元素怎么办呢？
如果一个元素从队首开始t人
如果队首没有过期 其他的元素你管他干嘛？又不是答案，现在又用不到
如果队首过期，那就t掉他继续t下一个 直到找到一个没有过期的，然后参考上一步就OK了

while((head <= tail)&&(v[head].pos < i - m))
            head++;

接下里贴代码

手写版：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int n,m;
inline int rd()
{
    int data = 0;
    int f = 1;
    char ch = getchar();
    while(ch < '0'||ch > '9')
    {
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0'&&ch <= '9')
    {
        data = (data<<3) + (data<<1) + ch - '0';
        ch = getchar();
    }
    return f * data; 
}
int a[2000010];
int min_que[2000010];
struct node
{
    int val;
    int pos;
}v[2000010];
void write(int x)
{
    if(x > 10)
        write(x/10);
    putchar(x%10 + '0');	
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n;i++)
        a[i] = rd();
    int head = 1,tail = 0;
    min_que[0] = 0;
    for(int i = 1;i < n;i++)
    {
        while((head <= tail)&&(v[tail].val >= a[i - 1]))
            tail--;
        v[++tail].val = a[i - 1];
        v[tail].pos = i - 1;
        while((head <= tail)&&(v[head].pos < i - m))
            head++;
        min_que[i] = v[head].val;
    }
    for(int i = 0;i < n;i++)
        printf("%d\n",min_que[i]);
}

STL版：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<deque>
using namespace std;
const int maxsize = 2000010;
int n,m;
struct node
{
    int val;
    int pos;
}A[maxsize];
deque<node> min_Q;
inline int rd()
{
    int data = 0;
    int f = 1;
    char ch = getchar();
    while(ch < '0'||ch > '9')
    {
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0'&&ch <= '9')
    {
        data = (data<<3) + (data<<1) + ch - '0';
        ch = getchar();
    }
    return f * data; 
}
int min_que[maxsize]; 
int main()
{
    n = rd(),m = rd();
    for(int i = 1;i <= n;i++)
    {
        A[i].val = rd();
        A[i].pos = i - 1;
    }
    min_que[0] = 0;
    for(int i = 1;i < n;i++)
    {
        while(!min_Q.empty()&&min_Q.back().val >= A[i].val)
            min_Q.pop_back();
        min_Q.push_back(A[i]);
        while(!min_Q.empty()&&min_Q.front().pos < i - m)
            min_Q.pop_front();
        min_que[i] = min_Q.front().val;
    }
    for(int i = 0;i < n;i++)
        printf("%d\n",min_que[i]);	
            
}

小小用了一下快读，不懂的同学可以直接用scanf代替
不要用cin会超时（除非你把std同步关掉）
如果这道题你过了，就可以看一下以下两题，都差不多，难度不会太大，注意边界条件就可以过了
传送门： P1886滑动窗口、P2032扫描

最后再介绍一下这个优先队列的作用，一般是用来优化DP，OI中较少直接仅仅考察该算法，同常都是和DP结合起来。