10分代码求助

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

lattice790 @ 2021-02-13 19:15:09

#include<bits/stdc++.h>
#include<cmath>
using namespace std;long long n,k;
    long long a[1000000];long long Min[1000000],Max[1000000];
int main()
{

    cin>>n>>k;
    for(long i=1;i<=n;i++) cin>>a[i];
    for(long j=1;(j+k-1)<=n;j++)
    {
        Min[j]=min(min(a[j],a[j+1]),a[j+2]);
        Max[j]=max(max(a[j],a[j+1]),a[j+2]);
    }
    for(long q=1;q<=(n-k+1);q++)
    {cout<<Min[q]<<' ';}
    cout<<endl;
    for(long p=1;p<=(n-k+1);p++)
    {cout<<Max[p]<<' ';}
    return 0;
}

by EuphoricStar @ 2021-02-13 19:17:00

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


by lattice790 @ 2021-02-13 19:21:59

可我寻思暴力就能解啊


by lattice790 @ 2021-02-13 19:26:56

@zltzlt


by 方123456 @ 2021-02-13 19:28:37

emmmm 我想不明白暴力为什么是这么写的,,,

这只能过 k=3 的情况吧。。。


by 方123456 @ 2021-02-13 19:29:46

显然有一个问题,就是无法完整遍历 j~j+k-1 这一个区间,如果再用一个循环遍历就 (大概) 会 TLE 。


by lattice790 @ 2021-02-13 19:33:00

哦,我发现了盲点


|