求助 return 3221225477
查看原帖
求助 return 3221225477
602527
star_maelstorm楼主2022/9/9 15:02
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+1;
typedef pair<int,int> PII;
int max_=-1;
int n,m1,m2;
int res1[maxn],res2[maxn];
struct range
{
	int arrive,department;
}na[maxn],in[maxn];
bool cmp(const range& x,const range& y)
{
	return x.arrive<y.arrive;
}
void solve(range* nain,int m,int* res)
{
	priority_queue<PII,vector<PII>,greater<PII>> leave;
	priority_queue<int,vector<int>,greater<int>> last_bridge;
	for(int i=1;i<=n;i++)
	{
		last_bridge.push(i);
	}
	for(int i=1;i<=m;i++)
	{
		while(!leave.empty()&&nain[i].arrive>=leave.top().first);
		{
			last_bridge.push(leave.top().second);
			leave.pop();
		}
		if(last_bridge.empty()) continue;
		int bridge=last_bridge.top();
		last_bridge.pop();
		res[bridge]++;
		leave.push(make_pair(nain[i].department,bridge));
	}
	for(int i=1;i<=n;i++)
	{
		res[i]+=res[i-1];
	}
}
int main()
{
	cin>>n>>m1>>m2;
	for(int i=1;i<=m1;i++)
	{
		cin>>na[i].arrive;
		cin>>na[i].department;
	}
	for(int i=1;i<=m2;i++)
	{
		cin>>in[i].arrive;
		cin>>in[i].department;
	}
	sort(na+1,na+m1+1,cmp);
	sort(in+1,in+m2+1,cmp);
	solve(na,m1,res1);
	solve(in,m2,res2);
	for(int i=0;i<=n;i++)
	{
		max_=max(max_,res1[i]+res2[n-i]);
	}
	cout<<max_<<endl;
	return 0;
}
2022/9/9 15:02
加载中...