RT,最大复杂度 O(nm) 的暴力水过去了
思路是先算出每架飞机如果要停靠在廊桥,最少需要多少个廊桥;然后再统计出每个廊桥停靠的飞机数量,求出来前缀和就是有 i 个廊桥时能停靠多少飞机。但是求的时候用的是暴力扫描已有的所有廊桥,找到第一个已经没有飞机的廊桥,显然会被卡到 O(nm)。
代码如下:(t1[i] 和 t2[i] 表示第 i 个廊桥停靠的飞机在什么时候离开,val1[i] 和 val2[i] 一开始表示停靠在第 i 个廊桥的飞机数量,求出前缀和后表示如果有 i 个廊桥能停靠多少飞机)
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m1,m2,ans=0,t1[100001],t2[100001],val1[100001],val2[100001];
struct air
{
int ar,le;
} a1[100001],a2[100001];
bool cmp(air x,air y)
{
return x.ar<y.ar;
}
void cal1()
{
for(int i=1;i<=m1;i++)
{
int now=1;
while(t1[now]>a1[i].ar) now++;
t1[now]=a1[i].le;
val1[now]++;
}
for(int i=1;i<=n;i++) val1[i]+=val1[i-1];
}
void cal2()
{
for(int i=1;i<=m2;i++)
{
int now=1;
while(t2[now]>a2[i].ar) now++;
t2[now]=a2[i].le;
val2[now]++;
}
for(int i=1;i<=n;i++) val2[i]+=val2[i-1];
}
int main()
{
scanf("%d%d%d",&n,&m1,&m2);
for(int i=1;i<=m1;i++)
scanf("%d%d",&a1[i].ar,&a1[i].le);
for(int i=1;i<=m2;i++)
scanf("%d%d",&a2[i].ar,&a2[i].le);
sort(a1+1,a1+1+m1,cmp);
sort(a2+1,a2+1+m2,cmp);
cal1();cal2();
for(int i=0;i<=n;i++)
ans=max(ans,val1[i]+val2[n-i]);
printf("%d",ans);
return 0;
}