数据过水

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 hytallenxu @ 2024-01-13 22:02:23

甚至快读都没加


by hytallenxu @ 2024-01-13 22:18:14

暴力使用快读记录 --558ms

正解使用快读记录 --666ms

难道这就是暴力踩标算


by Expert_Dream @ 2024-01-13 22:22:30

啊?


by Expert_Dream @ 2024-01-13 22:24:25

@hytallenxu 就是说你那个if判断很玄学,删了之后 TLE * 1


by Expert_Dream @ 2024-01-13 22:26:57

@hytallenxu 你的代码时间复杂度是 O(n/k) 的吧?估计出题人没有造n=1e6,k=1的数据,你可以造一个,然后让管理添加hack


by hytallenxu @ 2024-01-13 22:27:33

@gsczl71 ok 谢谢大佬


by hytallenxu @ 2024-01-13 22:28:34

@gsczl71 但是这样不就是1e6了吗,还是可以过吧 awa


by Expert_Dream @ 2024-01-13 22:30:39

@hytallenxu 不对,是n^2/k吧

我是那么认为,你每次得要最劣情况得要跳k步?还是咋样,我感觉我也不太清楚了。


by hytallenxu @ 2024-01-13 22:36:01

@gsczl71 hh

https://www.luogu.com.cn/problem/U397530

按照您的说法造了,但是就 269ms


by hytallenxu @ 2024-01-13 22:36:23

@gsczl71 没关流同步甚至


| 下一页