求一下,蒟蒻不会算复杂度
查看原帖
求一下,蒟蒻不会算复杂度
289436
LZX_ssfd楼主2021/10/27 16:57

|| 烦帮忙算一下复杂度

代码代码

#include<bits/stdc++.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define For(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=1e5+5;
int n,m1,m2;
struct plane{
	int l,r;
}a[N];
bool cmp(plane x,plane y){
	return x.l<y.l;
}
plane b[N];
int lay_down_a[N];
int lay_down_b[N];
int Fa[N],Fb[N];
vector<int >aa,bb;
int main(){
	freopen("airport.in","r",stdin);
	freopen("airport.out","w",stdout);
	scanf("%d%d%d",&n,&m1,&m2);
	For(i,1,m1)scanf("%d%d",&a[i].l,&a[i].r),lay_down_a[i]=i,aa.push_back(0);
	For(i,1,m2)scanf("%d%d",&b[i].l,&b[i].r),lay_down_b[i]=i,bb.push_back(0);
	sort(a+1,a+m1+1,cmp);
	sort(b+1,b+m2+1,cmp);
	For(i,1,m1){
		For(j,0,i-1)
			if(a[i].l>aa[j])
			{
				lay_down_a[i]=j+1;
				aa[j]=a[i].r;
				break;
			}
		Fa[lay_down_a[i]]++;
	}
	For(i,1,m2){
		For(j,0,i-1)
			if(b[i].l>bb[j])
			{
				lay_down_b[i]=j+1;
				bb[j]=b[i].r;
				break;
			}
		Fb[lay_down_b[i]]++;
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		Fa[i]+=Fa[i-1];
		Fb[i]+=Fb[i-1];
	}
	for(int i=0;i<=n;i++)ans=max(ans,Fa[i]+Fb[n-i]);
	printf("%d\n",ans);
	return 0;
}
2021/10/27 16:57
加载中...