暴力前缀和95pts求调
查看原帖
暴力前缀和95pts求调
654958
Light_az楼主2022/10/4 21:02

Rt

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m1,m2;
int s1[N],f1[N],end1[N],k1=0;
int s2[N],f2[N],end2[N],k2=0;
struct plane{
	int str,end;
}p1[N],p2[N];
bool cmp(plane a,plane b){
	return a.str<b.str;
}
int main(){
	cin>>n>>m1>>m2;
	for(int i=1;i<=m1;i++){
		cin>>p1[i].str>>p1[i].end;
	}
	for(int i=1;i<=m2;i++){
		cin>>p2[i].str>>p2[i].end;
	} 
	sort(p1+1,p1+1+m1,cmp);
	sort(p2+1,p2+1+m2,cmp);
	for(int i=1;i<=m1;i++){
		int flag=0;
		for(int j=1;j<=k1;j++){
			if(p1[i].str>end1[j]){
				end1[j]=p1[i].end;
				s1[j]++;
				flag=1;
				break;
			} 
		}
		if(!flag){
			end1[++k1]=p1[i].end;
			s1[k1]++;
		}
	}
	for(int i=1;i<=m2;i++){
		int flag=0;
		for(int j=1;j<=k2;j++){
			if(p2[i].str>end2[j]){
				end2[j]=p2[i].end;
				s2[j]++;
				flag=1;
				break;
			} 
		}
		if(!flag){
			end2[++k2]=p2[i].end;
			s2[k2]++;
		}
	}
	for(int i=1;i<=n;i++){
		f1[i]=f1[i-1]+s1[i];
		f2[i]=f2[i-1]+s2[i];
	}
	int ans=0;
	for(int i=0;i<=n;i++){
		ans=max(ans,f1[i]+f2[n-i]);
	}
	cout<<ans;
	return 0;
}
2022/10/4 21:02
加载中...