35分TLE求助
查看原帖
35分TLE求助
839896
ttx420229楼主2023/10/14 11:45
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int MAXN=500001;
int n,m1,m2;
struct g{
	int a;//进入时间 
	int b;//离开时间 
};
g s1[MAXN];
g s2[MAXN];
void paixu1(){//对国内进入时间排序 
	for(int i=1;i<=m1;i++){
		for(int j=i;j<=m1;j++){
			if(s1[i].a>s1[j].a){
				swap(s1[i],s1[j]);
			}
		}
	}
} 
void paixu2(){//对国际进入时间排序 
	for(int i=1;i<=m2;i++){
		for(int j=i;j<=m2;j++){
			if(s2[i].a>s2[j].a){
				swap(s2[i],s2[j]);
			}
		}
	}
} 
int can_in(int w,int arr[],int r){//计算进入了哪个廊桥,并标注离开时间 
	for(int i=1;i<r;i++){
		if(w>arr[i])//如果进入时间大于上一架飞机的离开时间,将这座飞机放入廊桥中并取代上一座飞机离开时间 
		return i; //记录进入几号廊桥 
	}
	return 0;
}
int plane(int q){//廊桥数量 
	int ans=0;
	int e1[q+1]={0},e2[n-q+1]={0};//e1表国内可停靠廊桥,e2表国际可停靠廊桥 
	for(int i=1;i<=m1;i++){
		if(i>=q+1){
			int c=can_in(s1[i].a,e1,q+1);
			if(c!=0){
				e1[c]=s1[i].b;
				ans++;
			}
		} 
		else {
			e1[i]=s1[i].b;
			ans++;
		}
	} 
	for(int i=1;i<=m2;i++){
		if(i>=n-q+1){
			int c=can_in(s2[i].a,e2,n-q+1);
			if(c!=0){
				e2[c]=s2[i].b;
				ans++;
			}
		}
		else {
			e2[i]=s2[i].b;
			ans++;
		}
	} 
	return ans;
}
int main(){
	//freopen("airport.in","r",stdin);
	//freopen("airport.ans","w",stdout);
	int maxx=0;
	scanf("%d%d%d",&n,&m1,&m2);
	for(int i=1;i<=m1;i++){
		scanf("%d%d",&s1[i].a,&s1[i].b);//输入国内航班 
	}
	paixu1();
	for(int i=1;i<=m2;i++){
		scanf("%d%d",&s2[i].a,&s2[i].b);//输入国际航班 
	}
	paixu2();
	for(int i=0;i<=n;i++){
		int o=plane(i);
		if(o>maxx)
		maxx=o;
	} 
	printf("%d",maxx);
	return 0;
}
2023/10/14 11:45
加载中...