wret4d @ 2018-08-05 19:00:33
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int n,k;
struct t
{
int a,num;
bool operator > (const t& x)const
{
return x.a<a;
}
bool operator < (const t& x)const
{
return x.a>a;
}
}b[1000001];
priority_queue <t> q1;
priority_queue <t,vector <t> ,greater <t> > q2;
int main()
{
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i].a);
b[i].num=i;
if(i<k)
{
q1.push(b[i]);
q2.push(b[i]);
}
}
for(int i=k;i<=n;i++)
{
q2.push(b[i]);
while(q2.top().num<=i-k)
{
q2.pop();
}
printf("%d ",q2.top());
}
printf("\n");
for(int i=k;i<=n;i++)
{
q1.push(b[i]);
while(q1.top().num<=i-k)
{
q1.pop();
}
printf("%d ",q1.top());
}
return 0;
}
by wret4d @ 2018-08-05 19:04:43
同一篇代码还能交出80分,最后一个点也TLE。为什么?求解!
by 心杭 @ 2018-08-05 19:22:57
你的代码N(n^2)耗时过长过不去。
by 心杭 @ 2018-08-05 19:25:27
你再研究一下,可以N(n*logn)的
by _FILARET_ @ 2018-08-05 19:42:34
@心杭 O(n^2)和O(n*log(n))吧
by 心杭 @ 2018-08-05 19:43:43
我,唉!!