真惊悚

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

gztony @ 2020-11-12 19:46:48

这是我见过最bian//tai的题目了！因为我第九个测试点超时，所以我下载了数据，没想到下载的时候网页居然崩了！之后我看了一下网页，数据是这个大啊…… 没想到在操作中心测试后，操作中心也崩了！我是不是该换台电脑了……

by gztony @ 2020-11-12 19:48:07

这里附上暴力代码

#include<bits/stdc++.h>
using namespace std;
int a[1000000],m1[1000000],m2[1000000];
int main(){
    long long i,j,ma=-4294967296,mi=4294967296,n,k;
    cin>>n>>k;
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    for(i=0;i<=n-k;i++){
        for(j=i;j<i+k;j++){
            if(ma<a[j])ma=a[j];
            if(mi>a[j])mi=a[j];
        }
        m1[i]=ma;
        m2[i]=mi;
        ma=-4294967296;
        mi=4294967296;
    }
    for(i=0;i<=n-k;i++){
        cout<<m2[i]<<" ";
    }
    cout<<endl;
    for(i=0;i<=n-k;i++){
        cout<<m1[i]<<" ";
    }
    return 0;
}

by zhanghzqwq @ 2020-11-12 19:48:50

@gztony 你是用暴力做的？

by gztony @ 2020-11-12 19:53:19

@zhanghanzhang 对，我不太想拘泥于队列（°_°）~~其实就是懒~~

by Ryo_Yamada @ 2020-11-12 19:56:16

@gztony 这就叫不拘泥于

建议学习时间复杂度

by zhanghzqwq @ 2020-11-12 19:57:25

另，暴力能拿90分我很震惊（

by Aw顿顿 @ 2020-11-12 20:01:17

暴力 90pts 怎么做到的？

by AMIRIOX無暝 @ 2020-11-12 20:01:50

那啥,网页会不会卡和数据规模关系不大, 首先可能只有一个 n 然后1e9, 其次我见过最大的数据点文件也就1.x MB, devcpp的installer就70几M了把

by oistr @ 2020-11-12 20:03:34

lz 暴力拿了 90pts，建议加强数据（逃

by w23c3c3 @ 2020-11-12 20:11:07

线段树都过了（雾