关于复杂度分析 & 常数
查看原帖
关于复杂度分析 & 常数
313716
EgLund楼主2021/10/24 00:29

我觉得我的复杂度是 O(m1logm1+m2logm2+n)\mathcal O(m_1 \log m_1+m_2 \log m_2+n) 的,喜提40。是不是 STL 常数太大了还是什么不可告人的原因导致 TLE?

#include<algorithm>//airport
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,m1,m2;
struct airline
{
    int s,e;
    bool operator<(airline const& other){return s<other.s;}
}domes[100009],inter[100009];
int domv[100009],intv[100009];
int domnxt[100009],intnxt[100009];
int domsiz[100009],intsiz[100009];
int domqzh[100009],intqzh[100009];
queue<int>domh,inth;
int main()
{
//freopen(...)
    ios::sync_with_stdio(0);
    cin>>n>>m1>>m2;
    for(int i=1;i<=m1;i++)cin>>domes[i].s>>domes[i].e;
    sort(domes+1,domes+m1+1);
    int siz1=0;
    while(siz1<m1)
    {
        int last=-1,lastval=0,head=0;
        for(int i=1;i<=m1;i++)if(domes[i].s>last && domv[i]==0)
        {
            if(last==-1)domh.push(i),head=i;
            domv[i]=1;
            domnxt[lastval]=i;
            last=domes[i].e;
            lastval=i;
            domsiz[head]++;
            siz1++;
        }
    }
    for(int i=1;i<=m2;i++)cin>>inter[i].s>>inter[i].e;
    sort(inter+1,inter+m2+1);
    int siz2=0;
    while(siz2<m2)
    {
        int last=-1,lastval=0,head=0;
        for(int i=1;i<=m2;i++)if(inter[i].s>last &&intv[i]==0)
        {
            if(last==-1)inth.push(i),head=i;
            intv[i]=1;
            intnxt[lastval]=i;
            last=inter[i].e;
            lastval=i;
            intsiz[head]++;
            siz2++;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(domh.empty())domqzh[i]=domqzh[i-1];
        else domqzh[i]=domqzh[i-1]+domsiz[domh.front()],domh.pop();
        if(inth.empty())intqzh[i]=intqzh[i-1];
        else intqzh[i]=intqzh[i-1]+intsiz[inth.front()],inth.pop();
    }
    int ans=-1;
    for(int i=1;i<=n;i++)ans=max(ans,domqzh[i]+intqzh[n-i]);
    cout<<ans;
    return 0;
}

2021/10/24 00:29
加载中...