蒟蒻求助

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

Ich_liebe_dich @ 2019-09-06 14:04:03

萌新离线求助 这题不用单调队列能不能过 这个代码老是被最大三个点卡 能不能帮忙极限优化一下QAQ

#include<iostream>
#include<queue>
#include<map>
using namespace std;

int main()
{
    long long n,k,i,qstore;
    map<long long,long long> counter;
    map<long long,long long>::iterator x;
    queue<long long> answer1,answer2,store;
    cin>>n>>k;

    for(i=1;i<=k;++i)
        cin>>qstore,
        ++counter[qstore],
        store.push(qstore);

    for(;i<=n;++i)
    {
        answer1.push(counter.begin()->first);
        answer2.push(counter.rbegin()->first);
        x=counter.find(store.front());
        if(x->second==1)
            counter.erase(x);
        else
            --x->second;
        store.pop();

        cin>>qstore;
        store.push(qstore);
        ++counter[qstore];
    }
    answer1.push(counter.begin()->first);
    answer2.push(counter.rbegin()->first);

    while(!answer1.empty())
        cout<<answer1.front()<<' ',
        answer1.pop();
    cout<<'\n';
    while(!answer2.empty())
        cout<<answer2.front()<<' ',
        answer2.pop();

    counter.clear();
    return 0;
}

by Ich_liebe_dich @ 2019-09-06 14:06:10

开了O2之后只爆了一个点,是不是哪里可以再优化一下QAQ


by pzc2004 @ 2019-09-06 14:15:15

线段树多好


by Lskkkno1 @ 2019-09-06 14:25:06

@Ich_liebe_dich map 应该比较慢,要不换 priority\_queue 试一试


by Lskkkno1 @ 2019-09-06 14:28:04

emmm...应该主要还是输入太慢了

加一个

ios::sync_with_stdio(false);

救星


by Lskkkno1 @ 2019-09-06 14:29:03

https://blog.csdn.net/weixin_44231491/article/details/90343744


by 1saunoya @ 2019-09-06 14:35:34

@Lskkkno1

要加就加三件套

ios :: sync_with_stdio(0) ;
cin.tie(0) , cout.tie(0) ;

by 矢信 @ 2019-09-06 15:46:52

这道题不是可以用二叉堆吗


|