20WA求调

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

121121a @ 2024-03-22 21:28:04

#include<iostream>
#include<stack>
using namespace std;
int n,m;
int qmin[1000005],qmax[1000005],a[1000005];
int min_deque(){
    int h=1,t=1;
    for(int i=1;i<=n;i++){
        while(h <=t && qmin[h]+m <= i){
            h++;
        }
        while(h <=t && a[i] <= a[qmin[h]]){
            t--;
        }
        qmin[++t]=i;
        if(i >= m){
            cout<<a[qmin[h]]<<' ';
        }
    }
    cout<<endl;
    return 0;
}
int max_deque(){
    int h=1,t=0;
    for(int i=1;i<=n;i++){
        while(h <=t && qmax[h]+m <= i){
            h++;
        }
        while(h <=t && a[i] >= a[qmax[h]]){
            t--;
        }
        qmax[++t]=i;
        if(i >= m){
            cout<<a[qmax[h]]<<' ';
        }
    }
    return 0;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    min_deque();
    max_deque();
}

by ztksc07 @ 2024-03-22 22:27:38

样例就错了啊喂()


by ztksc07 @ 2024-03-22 22:35:59

while(h <=t && a[i] <= a[qmin[h]]){
            t--;
        }

改为

while(h <=t && a[i] <= a[qmin[t]]){
            t--;
        }

下面同理


by 121121a @ 2024-03-23 13:49:29

@ZtkLeo 谢谢


|