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
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
这道题不是可以用二叉堆吗