为什么第二个点TLE?求助求助!!!

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

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

我,唉!!


|