数据过水

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

hytallenxu @ 2024-01-13 22:02:01

rt,以下是我的暴力代码:

#include <iostream>
#include <cstring>
using namespace std;

int mini[1000010],maxi[1000010];
int main(){
    int n,a[1000010],k;

    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mini[i]=1e9;
        maxi[i]=-1e9;
    }
    for(int i=1;i<=n-k+1;i++){
        if((a[i-1]==mini[i-1] or a[i-1]==maxi[i-1] or a[i+k-2]==mini[i-1] or a[i+k-2]==maxi[i-1]) or (mini[i-1]==0 or maxi[i-1]==0) or (a[i]<mini[i-1] or a[i]>maxi[i-1] or a[i+k-1]<mini[i-1] or a[i+k-1]>maxi[i-1])) {
                for(int j=i;j<=i+k-1;j++) {
                    mini[i]=min(mini[i],a[j]);
                    maxi[i]=max(maxi[i],a[j]);
                }
        }else{
            mini[i]=mini[i-1];
            maxi[i]=maxi[i-1];
        }

    }
    for(int i=1;i<=n-k+1;i++) cout<<mini[i]<<" ";
    cout<<"\n";
    for(int i=1;i<=n-k+1;i++) cout<<maxi[i]<<" ";
    return 0;
}

然后他过了,评测记录


by adam01 @ 2024-01-13 22:41:35

@hytallenxu

1000000 500000
1 1 1 1 ...

就卡掉了。


by tiger2008 @ 2024-01-13 23:15:42

玄学特判

k小一点就可以卡掉(

数据可能是水了些(


上一页 |