40分求助!!

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

2022_37_yzyUUU @ 2023-07-14 15:57:32

#include<bits/stdc++.h>
using namespace std;
int a[1000001],n,k,maxn[1000001],minn[1000001];
int maxx(int f,int l){
    int m=a[f];
    for(int i=f+1;i<=l;i++)if(a[i]>m)m=a[i];
     return m;
}
int minx(int f,int l){
    int m=a[f];
    for(int i=f+1;i<=l;i++)if(a[i]<m)m=a[i];
    return m;
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n-k+1;i++){
        for(int j=i;j<=i+k-1;j++){
            minn[i]=minx(i,i+k-1);
            maxn[i]=maxx(i,i+k-1);
        }
    }
    for(int i=1;i<=n-k+1;i++)cout<<minn[i]<<" ";
    cout<<endl;
    for(int i=1;i<=n-k+1;i++)cout<<maxn[i]<<" ";
    return 0;
}

by _Haoomff_ @ 2023-07-14 15:59:59

@2022_37_yzyUU 这肯定过不了啊,时间复杂度太高了


by 2022_37_yzyUUU @ 2023-07-18 17:42:59

@Haoomff 怎么办??!!


|