问个问题

P1886 滑动窗口 /【模板】单调队列

Fractures @ 2019-08-16 20:27:20

萌新打了会单调队列的代码(滑动窗口求最小值),但是为什么输出结果不太一样呢

#include<cstdio>
#include<iomanip>
#include<queue>
const int MAXN=110000001;
using std::deque;
struct num{
    int index,x;
};
int a[MAXN];
int n,m;
deque<num>q;
num t;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        t.index=i;
        t.x=a[i];
        if(q.empty()){
            printf("0 ");
        }
        else{
            if(q.front().index+m<i){
                q.pop_front();
            }
            printf("%d ",q.front().x);
        }
        while((!q.empty())&&q.back().x>=a[i]){
            q.pop_back();
        }
        q.push_back(t);
    }
    return 0;
}

输入:

8 3 
1 3 -1 -3 5 3 6 7

应该输出:

-1 -3 -3 -3 3 3

实际输出:

0 1 1 -1 -3 -3 -3 3 

by t162 @ 2019-08-16 20:29:14

显然


by t162 @ 2019-08-16 20:30:17

细节:窗口的大小必须为k


by Cwling @ 2019-08-16 20:30:24

大佬您的码风以及单调队列的形式蒟蒻我欣赏不来


by muyang_233 @ 2019-08-16 20:46:03

窗口大小必须为k


by Fractures @ 2019-08-16 21:03:42

qaq


|