一种神奇的思路,想看看有没有出路
查看原帖
一种神奇的思路,想看看有没有出路
476473
naturelyf楼主2024/10/24 21:30
#include<bits/stdc++.h>
#define PII pair<int,int>

#define sta first

#define out second

using namespace std;
const int N=1e5+10;
int n,m1,m2;
int read(){
	char ch;
	int x=0,f=1;
	ch=getchar();
	while(ch<'0'||'9'<ch){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
PII dt[N];
int t[3][N],s,cnt;
int fa[N];
int find(int x){
	if(x==fa[x])return x;
	return fa[x]=find(fa[x]);
}
void init(int k){
	for(int i=1;i<=k+1;i++)fa[i]=i,s=0,cnt=0,dt[i].sta=0,dt[i].out=0;
	
}
void work(int k,int p){
	init(k);
	for(int i=1;i<=k;i++)
		dt[i].sta=read(),dt[i].out=read();
	sort(dt+1,dt+k+1);
	while(s<k){
		int r=0;
		cnt++;
		t[p][cnt]=t[p][cnt-1];
		for(int i=find(1);i<=k;i=find(i+1)){
			if(r<dt[i].sta){
				r=dt[i].out;
				s++;
				t[p][cnt]++;
				fa[find(i)]=fa[find(i+1)];
			}
		}
	}
//	for(int i=1;i<=cnt;i++)cout<<t[p][i]<<" ";
//	puts("");
}
int main(){
//	freopen("airport.in","r",stdin);
//	freopen("airport.out","w",stdout);
	n=read(),m1=read(),m2=read();
	work(m1,1);
	work(m2,2);
	int ans=0;
	for(int i=0;i<=n;i++)ans=max(t[1][i]+t[2][n-i],ans);
	cout<<ans;
	return 0;
}
//??£? n^2
//?éò?·¢??£o??′?é?μ?2???μtμ?°à′?£??í?àμ±óú?àò???o????¥
//é?á???oó2¢2é?ˉ???¤£?fa[find(i)]=fa[find(i+1)]£? 

每次扫一遍相当于加一个站点,然后并查集优化

2024/10/24 21:30
加载中...