求助,WA on #3

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

Elairin176 @ 2022-10-05 18:22:07

单调队列做法

#include <deque>
#include <iostream>
using namespace std;
#define int long long
struct windows{
    int number;
    int label;
};
int n,k,maxarr[60000010],iii=0;
windows arr[60000010];
signed main(void){
    cin>>n>>k;
    deque<windows>mindeque;
    deque<windows>maxdeque;
    for(int i=0;i<n;i++){
        cin>>arr[i].number;
        arr[i].label=i;
    }
    for(int i=0;i<n;i++){
        if(i==0){
            mindeque.push_back(arr[i]);
            maxdeque.push_back(arr[i]);
        }else{
            while(!mindeque.empty()&&mindeque.back().number<=arr[i].number){
                mindeque.pop_back();
            } 
            mindeque.push_back(arr[i]); 
            while(i>=mindeque.front().label+k) mindeque.pop_front();
            if(i>=k-1) maxarr[iii++]=mindeque.front().number;
            while(!maxdeque.empty()&&maxdeque.back().number>=arr[i].number){
                maxdeque.pop_back();
            } 
            maxdeque.push_back(arr[i]); 
            while(i>=maxdeque.front().label+k) maxdeque.pop_front();
            if(i>=k-1) cout<<maxdeque.front().number<<" ";
        }
    }
    cout<<endl;
    for(int i=0;i<iii;i++) cout<<maxarr[i]<<" ";
}

by bamboo12345 @ 2022-10-05 18:56:43

@destructor k=1呢?


by Elairin176 @ 2022-10-05 18:58:59

@bamboo123 嗯,我调调


by Elairin176 @ 2022-10-05 19:04:35

@bamboo123 好了,A了,谢谢指点


|