蒟蒻90pts,TLE求调

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

conj @ 2024-10-04 16:22:46

rt.

#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000005];
int mina[1000005],maxp[1000005];
int amx(int a[],int b,int c){
    int maxi=-2147483648;
    for(int i=c;i<b;i++){
        if (maxi<a[i]){
            maxi=a[i];
        }
    }

    return maxi;
}
int amn(int a[],int b,int c){
    int maxa=2147483647;
    for(int i=c;i<b;i++){
        if (maxa>a[i]){
            maxa=a[i];
        }
    }
    return maxa;
}
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n-k+1;i++){
        mina[i]=amn(a,i+k,i);
        maxp[i]=amx(a,i+k,i);
    }
    for(int i=0;i<n-k+1;i++){
       cout<<mina[i]<<" ";
    }
    cout<<endl;
    for(int i=0;i<n-k+1;i++){
       cout<<maxp[i]<<" ";
    }

    return 0;
}

by llamn @ 2024-10-04 16:23:45

cin怎敢


by Libingyue2011 @ 2024-10-04 16:24:47

哥们,你是暴力 O(nk) 过不了。


by xuezhiyu @ 2024-10-04 16:25:05

斯——单调队列的题你暴力90pts?卡常之神


by Libingyue2011 @ 2024-10-04 16:25:36

需要 O(n)O(n\log n) 算法。

比如,堆,线段树,单调队列。


by Nake_fu @ 2024-10-04 16:27:18

在卡时间的话,可以用快读优化,但是这道题是单调队列


|