手写队列会超时吗?

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

Cong256 @ 2024-02-01 22:37:55

#include<bits/stdc++.h>
using namespace std; 
const int N=1e6+5;      
int qu[N];
int n,m;
int head=1,last=0;
int a[N],mx[N],mn[N];
int max_(int h,int l){
    int mx=0;
    for(int i=h;i<=l;i++){
        mx=max(mx,qu[i]);
    }
    return mx;
}
int min_(int h,int l){
    int mn=0x3f3f3f3f;
    for(int i=h;i<=l;i++){
        mn=min(mn,qu[i]);
    }
    return mn;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>qu[i];
    }
    last+=m;
    for(int i=1;i<=n-m+1;i++){
        mx[i]=max_(head,last);
        mn[i]=min_(head,last);
        last++;
        head++;
    }
    for(int i=1;i<=n-m+1;i++)
        cout<<mn[i]<<' ';
    cout<<endl;
    for(int i=1;i<=n-m+1;i++)
        cout<<mx[i]<<' ';
}

by JOKER_chu @ 2024-02-18 21:07:15

@xiaohaibao

这不是正解,正解是单调队列,你这是暴力


by Cong256 @ 2024-02-24 18:18:46

ok


|