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

dH_Hb · 2024-07-10 11:30:07 · 题解

什么！你不会单调队列就想做这道题！真是痴心妄想有勇气，看题解里没一篇暴力的，那我来水一篇吧！

注：非正解

话不多说，上代码（非正解我就不解释了）！

#include <bits/stdc++.h>
using namespace std;
const long long N=1000008;
long long n,k,a[N],da[N],xiao[N];
int main(){

    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n-k+1;i++){
        long long maxn=a[i],minn=a[i];
        if(a[i+k-1]>=da[i-1]&&i!=1){ //如果新的数>=上次窗口的最大值 
            da[i]=a[i+k-1];
        }else if(a[i-1]!=da[i-1]&&i!=1){
            da[i]=da[i-1];
        }else{
            for(int j=i;j<k+i;j++){
                maxn=max(maxn,a[j]);
            }
            da[i]=maxn;
        }
        if(a[i+k-1]<=xiao[i-1]&&i!=1){
            xiao[i]=a[i+k-1];
        }else if(a[i-1]!=xiao[i-1]&&i!=1){
            xiao[i]=xiao[i-1];
        }else{
            for(int j=i;j<k+i;j++){
                minn=min(minn,a[j]);
            }
            xiao[i]=minn;
        }
    }
    for(int i=1;i<=n-k+1;i++){
        cout<<xiao[i]<<" ";
    }
    cout<<endl;
    for(int i=1;i<=n-k+1;i++){
        cout<<da[i]<<" ";
    }

    return 0;
}