求大佬分析时间复杂度,只有20分
查看原帖
求大佬分析时间复杂度,只有20分
207671
王烨楼主2021/10/24 09:07
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
struct node{
	int l,r;
}a1[N],a2[N];
int lv1[N],lv2[N];
int n,m1,m2;
bool cmp(node x,node y)
{
	return x.l<y.l;
}
int solve(int l,int r)
{
	int ans1=0,ans2=0;
	int cnt1=0,cnt2=0;
	memset(lv1,0,sizeof(lv1));
	memset(lv2,0,sizeof(lv2));
	if(l!=0)
	{
		cnt1++;
		lv1[cnt1]=a1[1].r;
		ans1++;
		for(int i=2;i<=m1;i++)
	    {
		    bool flag=false;
			for(int j=1;j<=cnt1;j++)
		        if(lv1[j]<=a1[i].l)
		        {
			        lv1[j]=a1[i].r;
			        ans1++;
			        flag=true;
			        break;
				}
			if(flag) continue;
			else if(cnt1<l)
			{
				cnt1++;
				lv1[cnt1]=a1[i].r;
				ans1++;
			}
		}       
	}
	if(r!=0)
	{
		cnt2++;
		lv2[cnt2]=a2[1].r;
		ans2++;
		for(int i=2;i<=m2;i++)
	    {
		    bool flag=false;
			for(int j=1;j<=cnt2;j++)
		        if(lv2[j]<=a2[i].l)
		        {
			        lv2[j]=a2[i].r;
			        ans2++;
			        flag=true;
			        break;
				}
			if(flag) continue;
			else if(cnt2<r)
			{
				cnt2++;
				lv2[cnt2]=a2[i].r;
				ans2++;
			}
		}       
	}
	return ans1+ans2;
}
int main()
{
	freopen("airport.in","r",stdin);
	freopen("airport.out","w",stdout);
	scanf("%d%d%d",&n,&m1,&m2);
	for(int i=1;i<=m1;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		a1[i]={l,r};
	}
	for(int i=1;i<=m2;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		a2[i]={l,r};
	}
	sort(a1+1,a1+m1+1,cmp);
	sort(a2+1,a2+m2+1,cmp);
	int res=0;
	for(int i=0;i<=n;i++) res=max(res,solve(i,n-i));
	cout<<res<<endl;
	return 0;
}
2021/10/24 09:07
加载中...