洛谷 P1440 求m区间内的最小值(单调队列)

题目链接

https://www.luogu.org/problemnew/show/P1440

显然是一道单调队列题目……

解题思路

对于单调队列不明白的请看这一篇博客:https://www.cnblogs.com/yinyuqin/p/10492882.html

这道题和模板唯一的不同点就是从0开始，一直输出n次。什么意思呢？

普通单调队列：单调队列中数据到达m个再输出
本题：从没有数据时就开始输出。

详细点说，就是输出0到0，0到1，0到2……一直到0到m-1，接着是1到m，2到m+1，3到m+2……一直到n-m到n-1的最小值。

具体可以研究一下样例，很容易就可以理解。

所以我们只需要在输出上做一点修改。

如果队列为空，说明这是第一个元素，就输出0到0之间的最小值，显然是0。

否则就每次在读入一个数之前，就输出单调队列里面的最小值。

而且我们发现，最后读入的数其实是没有用的！！坑啊

艰辛的做题过程

首先是TLE：

找了好长时间的bug，没想到竟然是cin cout 搞的！！盘他

十年oi一场空，cin、cout见祖宗。

然后是莫名RE：

原来当m==1时，少判断了一个q.empty()会爆掉。。。

无语。。。。。

AC代码

 #include<iostream>

 #include<deque>

 #include<cstdio>

 using namespace std;

 int n,m;

 struct num{                        //储存每一个点的信息

     int  cnt,value;                //cnt是编号 value是值

     num(int a,int b):cnt(a),value(b){}//构造函数

 };

 deque<num> q;                    //定义一个双端队列,注意头文件

 void makeq(int i,int in){        //见另一篇博客

     if(q.empty()) q.push_back(num(i,in));

     else{

         num f=q.front();

         if(i>=f.cnt+m) q.pop_front();

         if(!q.empty()){            //注意判断队列是否为空

             num b=q.back();

             while(in<=b.value){

                 q.pop_back();

                 if(q.empty()) break;//注意再次判断队列是否为空

                 b=q.back();

             }

         }

         q.push_back(num(i,in));

     }

 }

 int main(){

     cin>>n>>m;

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

         if(q.empty()) printf("0\n");//第一个输出0

         else printf("%d\n",q.front().value);//后来每次输出单调队列的最小值

         int  in;

         scanf("%d",&in);            //注意用scanf

         makeq(i,in);                //让这个点入队

     }

     return ;

 }

巴特西