TLE80 MnZn求助

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

Nemonade @ 2021-08-23 16:19:28

RT，用的单调队列，感觉自己是正解啊。。。是不是有什么地方要优化的

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N],q[N],l,r=-1;
int n,k;
int main(){
    cin>>n>>k;
    for(int i=0;i<n;++i){
        cin>>a[i];
        if(i-k+1>q[l]) ++l;
        while(l<=r&&a[i]<=a[q[r]])--r;
        q[++r]=i;
        if(i+1>=k) cout<<a[q[l]]<<" ";
    }
    cout<<endl;
    l=0,r=-1;
    for(int i=0;i<n;++i){
        if(i-k+1>q[l]) ++l;
        while(l<=r&&a[i]>=a[q[r]]) --r;
        q[++r]=i;
        if(i+1>=k) cout<<a[q[l]]<<" ";
    }
    return 0;
}

by Nemonade @ 2021-08-23 16:20:34

#2 #10 TLE

by cq_loves_Capoo @ 2021-08-23 16:25:11

@nemonadeMC scanf

by cq_loves_Capoo @ 2021-08-23 16:25:30

@nemonadeMC cin 它不太行

by qwq___qaq @ 2021-08-23 16:26:04

@nemonadeMC 你好用，居然敢用cin/cout，用scanf/printf就 AC 了（连氧都不吸）：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N],q[N],l,r=-1;
int n,k;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;++i){
        scanf("%d",&a[i]);
        if(i-k+1>q[l]) ++l;
        while(l<=r&&a[i]<=a[q[r]])--r;
        q[++r]=i;
        if(i+1>=k) printf("%d ",a[q[l]]);
    }
    putchar('\n');
    l=0,r=-1;
    for(int i=0;i<n;++i){
        if(i-k+1>q[l]) ++l;
        while(l<=r&&a[i]>=a[q[r]]) --r;
        q[++r]=i;
        if(i+1>=k) printf("%d ",a[q[l]]);
    }
    return 0;
}

by _l_l_l_l_l_ @ 2021-08-23 16:33:20

除非读char 不然不要用cin/cout，拖后腿的超慢速读入

by Nemonade @ 2021-08-23 17:22:28

@窃月赠予卿天啊，scanf直接快了3000ms

by Acfboy @ 2021-08-23 20:10:49

@nemonadeMC 使用 iostream 里的内容可以加上一句

std::ios::sync_with_stdio(false);

以加快读写速度，但这样就不能再使用 cstdio 了。