为什么都是STLdeque,我却TLE了两个点,蒟蒻求救

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

xeri_chen @ 2019-06-10 21:52:33

#include<bits/stdc++.h>
#define N 2000001
using namespace std;

deque <int> dq;
deque <int> dq2;
int a[N],k,d[N],top;

void tj2(int x)
{
    while(!dq2.empty()&&a[dq2.back()]>a[x])
    {
        dq2.pop_back();
    }

    while(!dq2.empty()&&x-dq2.front()>=k) 
    {
        dq2.pop_front();
    }
    dq2.push_back(x);
}

void tj(int x)
{
    while(!dq.empty()&&a[dq.back()]<a[x])
    {
        dq.pop_back();
    }

    while(!dq.empty()&&x-dq.front()>=k) 
    {
        dq.pop_front();
    }
    dq.push_back(x);
}

int main()
{
    int n;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        tj(i);
        tj2(i);
        if(i>=k-1)
        {
            cout<<a[dq2.front()]<<" ";
            d[top++]=a[dq.front()];
        }   
    }
    cout<<endl;
    for(int i=0;i<top;i++)
        cout<<d[i]<<" ";
    return 0;   
}

by i207M @ 2019-06-10 22:26:38

不可以


by 越羽 @ 2019-06-10 22:32:43

试试加个ios::sync_with_stdio(0);


by Rbu_nas @ 2019-06-10 22:33:18

@2017BeiJiang 不可以,不能用,您可以去百度上搜一下这句话的意思


by zhangyuzhe @ 2019-06-10 22:40:13

@Rem,我这里可以


by Kirisame_Marisa_ @ 2019-06-10 22:48:54

@first_fan 不是因为保持和scanf,printf流的同步吗??

scanf,printf同样也要解析字符串,这上面速度不应该有大差距。


by first_fan @ 2019-06-10 22:51:10

@KirisameMarisa

谢谢提醒……差点因为自己无知误及他人QwQ……


by Clever_Jimmy @ 2019-07-10 14:26:29

@2017BeiJiang 不可以的


上一页 |