玄关求解答RE on #2

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

xpigeon @ 2024-12-17 17:07:06

为什么别的点过了#2RE了？数组也没开小吧？不知道自己犯了什么蠢问题求神犇解答 代码

#include<bits/stdc++.h>
using namespace std;
const int MN=1e6+10;
deque<int> ma;//维护最大值的队列 
deque<int> mi;//维护最小值的队列 
int a[MN],n,k;//a[i]为第i个数的值 
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    } 
    for(int i=1;i<=n;i++){//遍历每一个数 
        if(mi.front()==i-k){//掉出区间 
            mi.pop_front();
        }

        while(!mi.empty() && a[i]<a[mi.back()]){//队列不为空，且第i个数优于队尾
            mi.pop_back();//这个队尾可以滚了
        }

        mi.push_back(i);
        if(i>=k){
            cout<<a[mi.front()]<<" ";
        }
    }
    cout<<endl;
    for(int i=1;i<=n;i++){//遍历每一个数 
        if(ma.front()==i-k){
            ma.pop_front();//掉出区间 
        }
        while(!ma.empty() && a[i]>a[ma.back()]){//队列不为空，且第i个数优于队尾 
            ma.pop_back();//这个队尾可以滚了 
        } 
        ma.push_back(i);
        if(i>=k){
            cout<<a[ma.front()]<<" ";
        }
    }
    return 0;
}

by xpigeon @ 2024-12-17 17:35:04

好像说错了，是#3RE了

by BaiBaiShaFeng @ 2024-12-17 21:01:08

#include<bits/stdc++.h>
using namespace std;
const int MN=1e6+10;
deque<int> ma;//维护最大值的队列 
deque<int> mi;//维护最小值的队列 
int a[MN],n,k;//a[i]为第i个数的值 
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    } 
    for(int i=1;i<=n;i++){//遍历每一个数 
        while(!mi.empty() && a[i]<a[mi.back()]){//队列不为空，且第i个数优于队尾
            mi.pop_back();//这个队尾可以滚了
        }
        mi.push_back(i);
        if(mi.front()==i-k){//掉出区间 
            mi.pop_front();
        }
        if(i>=k){
            cout<<a[mi.front()]<<" ";
        }
    }
    cout<<endl;
    for(int i=1;i<=n;i++){//遍历每一个数 
        while(!ma.empty() && a[i]>a[ma.back()]){//队列不为空，且第i个数优于队尾 
            ma.pop_back();//这个队尾可以滚了 
        } 
        ma.push_back(i);    
        if(ma.front()==i-k){
            ma.pop_front();//掉出区间 
        }       
        if(i>=k){
            cout<<a[ma.front()]<<" ";
        }
    }
    return 0;
}

by BaiBaiShaFeng @ 2024-12-17 21:01:35

顺序错了哥，好好想想，画个图看看

by BaiBaiShaFeng @ 2024-12-17 21:01:44

@xpigeon

by xpigeon @ 2024-12-18 07:49:24

@BaiBaiShaFeng 还真是，太神了哥，爱你

by xpigeon @ 2024-12-18 07:49:57

此贴结

|