萌新求助,小根堆做法,45分。
查看原帖
萌新求助,小根堆做法,45分。
286448
Eason2009楼主2022/9/2 22:26
#include<bits/stdc++.h>
using namespace std;
int n,m1,m2,f1[100005],f2[100005];
struct node
{
	int st,ed;
}a[100005],b[100005];
bool cmp(node x,node y)
{
	return x.st<y.st;
}
void calc(node* c,int m,int* f)
{
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >lq;
	priority_queue<int,vector<int>,greater<int> >wq;
	for(int i=1;i<=n;i++)
	{
		wq.push(i);
	}
	for(int i=1;i<=m;i++)
	{
		if(!lq.empty()&&c[i].st>=lq.top().first)
		{
			wq.push(lq.top().second);
			lq.pop();
		}
		if(wq.empty()) continue;
		int res=wq.top();
		wq.pop();
		f[res]++;
		lq.push(make_pair(c[i].ed,res));
	}
	for(int i=1;i<=n;i++)
	{
		f[i]+=f[i-1];
	}
	return;
}
int main()
{
	cin>>n>>m1>>m2;
	for(int i=1;i<=m1;i++)
	{
		cin>>a[i].st>>a[i].ed;
	}
	for(int i=1;i<=m2;i++)
	{
		cin>>b[i].st>>b[i].ed;
	}
	sort(a+1,a+m1+1,cmp);
	sort(b+1,b+m2+1,cmp);
	calc(a,m1,f1);
	calc(b,m2,f2);
	int ans=0;
	for(int i=0;i<=n;i++)
	{
		ans=max(ans,f1[i]+f2[n-i]);
	}
	cout<<ans<<endl;
	return 0;
}
2022/9/2 22:26
加载中...