CSP2021-S T1 一半绿 一半红
  • 板块题目总版
  • 楼主LangQi99
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/7/19 20:06
  • 上次更新2023/10/27 19:27:51
查看原帖
CSP2021-S T1 一半绿 一半红
560128
LangQi99楼主2022/7/19 20:06
#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include<vector>
#define int long long
#define MAXN 500005 
using namespace std;

int n,m,ans[MAXN<<2],tag[MAXN<<2];
int m1,m2,g,b,chsex[MAXN],ansx0,as,ansy0,t,ansx[MAXN],mlx,mly,ansy[MAXN],chsey[MAXN];
int ansg[MAXN],ansp[MAXN];
struct node{
	int f;
	int t;
	int id;//当前飞机所在廊桥id 
	bool operator<(const node&x)const{
		return x.t<t;
	}
}x[MAXN],y[MAXN];
bool cmp(node a,node b){
	return a.f<b.f;
}
priority_queue<node> q;
priority_queue<int,vector<int>,greater<int> >id;
signed main(){
	cin>>n>>m1>>m2;
	for(int i=1;i<=m1;i++){
		cin>>g>>b;
		x[i].f=g;
		x[i].t=b;
	}
	sort(x+1,x+m1,cmp);
	for(int i=1;i<=m2;i++){
		cin>>g>>b;
		y[i].f=g;
		y[i].t=b;
	}
	sort(y+1,y+m2,cmp);


	for(int i=1;i<=n;i++){
		id.push(i);
	}
	for(int i=1;i<=m1;i++){
		while(!q.empty()&&x[i].f>q.top().t){//如果无覆盖 
			id.push(q.top().id);q.pop();//则id廊桥变为可用 
		}
		if(!id.empty()){//如果还有可用廊桥 
			q.push((node){x[i].f,x[i].t,id.top()});//安排飞机 
			ansg[id.top()]++; 
			id.pop();
		}
	}
	for(int i=0;i<n;i++){
		ansx[i+1]=ansx[i]+ansg[i+1];
	}
	
	while(!q.empty())
		q.pop();
	while(!id.empty())
		id.pop();
	
	for(int i=1;i<=n;i++){
		id.push(i);
	}
	for(int i=1;i<=m2;i++){
		while(!q.empty()&&y[i].f>q.top().t){//如果无覆盖 
			id.push(q.top().id);q.pop();//则id廊桥变为可用 
		}
		if(!id.empty()){//如果还有可用廊桥 
			q.push((node){y[i].f,y[i].t,id.top()});//安排飞机 
			ansp[id.top()]++; 
			id.pop();
		}
	}
	for(int i=0;i<n;i++){
		ansy[i+1]=ansy[i]+ansp[i+1];
	}
	for(int i=0;i<=n;i++){
		as=max(as,ansx[i]+ansy[n-i]);
	}
	cout<<as<<endl;
	return 0;
}

2022/7/19 20:06
加载中...