自动搬运

查看原文

来自洛谷，原作者为

	炳源 宜言饮酒，与子偕老。 琴瑟在御，莫不静好。

搬运于2025-08-24 21:25:06，当前版本为作者最后更新于2019-07-15 00:57:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

近学了单调队列，所以就用单调丢雷队列来做了
先分析一下题意
给出一个n个数的数列，要求m区间内的最小值
有点坑的就是第0个也要记录
所以很自然而然地想到了单调队列
有人说线段树牛逼，为啥不用线段树呢？

首先第一点：时间

对于单调队列来说，仅仅需要O（n）的时间扫一遍过去就可以了
但是对于线段树来说建树就需要nlogn的时间了
再加上一段一段的查询 时间开销一下子就大了起来

再看空间

线段树需要用到4*n的空间大小 挺大的
而单调队列仅仅只需要n的空间大小就可以了

最后代码长度

线段树需要的建树和查询需要多少和单调队列短短的五六行
一下子就可以看出来了

所以这道题我就是选用单调队列（dalao别嘲讽我，小蒟蒻一枚）

现在我们就开始讲讲单调队列到底是个什么东西吧

概念：

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

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结合起来。

当你在凝视算法的时候，算法也在凝视你