请求加强数据
查看原帖
请求加强数据
153687
donghanwen1225楼主2021/10/24 11:29

RT,最大复杂度 O(nm)O(nm) 的暴力水过去了
思路是先算出每架飞机如果要停靠在廊桥,最少需要多少个廊桥;然后再统计出每个廊桥停靠的飞机数量,求出来前缀和就是有 ii 个廊桥时能停靠多少飞机。但是求的时候用的是暴力扫描已有的所有廊桥,找到第一个已经没有飞机的廊桥,显然会被卡到 O(nm)O(nm)
代码如下:(t1[i]t_1[\text{i}]t2[i]t_2[\text{i}] 表示第 ii 个廊桥停靠的飞机在什么时候离开,val1[i]val_1[\text{i}]val2[i]val_2[\text{i}] 一开始表示停靠在第 ii 个廊桥的飞机数量,求出前缀和后表示如果有 ii 个廊桥能停靠多少飞机)

#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;
}
2021/10/24 11:29
加载中...