求助,请问为什么附件的第三个样例过不了
查看原帖
求助,请问为什么附件的第三个样例过不了
42424
deamoon_2楼主2021/10/26 21:21

应该是思路问题(?

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
int m,n1,n2;
int b1[100005],b2[100005];
int sum;
struct node{
	int v,t;
	bool operator < (const node &x)const{
		return x.v<v;
	}
};
priority_queue<node > q;
struct air{
	int l,r;
}a[100005];
bool cmp(air x,air y)
{
	return x.l<y.l;
}
int main()
{
	int x;
	scanf("%d%d%d",&m,&n1,&n2);
	for(int i=1;i<=n1;i++)
	scanf("%d%d",&a[i].l,&a[i].r);
	sort(a+1,a+n1+1,cmp);
	q.push((node){a[1].r,1});
	b1[0]=b1[1]=1;
	for(int i=2;i<=n1;i++)
	{
		if(a[i].l<q.top().v)
		{
			b1[++b1[0]]++;
			q.push((node){a[i].r,b1[0]});
		}
		else
		{
			x=q.top().t;
			b1[x]++;
			q.pop();
			q.push((node){a[i].r,x});
		}
	}
	for(int i=2;i<=n1;i++)
	b1[i]+=b1[i-1];
	while(!q.empty())
	q.pop();
	for(int i=1;i<=n2;i++)
	scanf("%d%d",&a[i].l,&a[i].r);
	sort(a+1,a+n2+1,cmp);
	q.push((node){a[1].r,1});
	b2[0]=b2[1]=1;
	for(int i=2;i<=n2;i++)
	{
		if(a[i].l<q.top().v)
		{
			b2[++b2[0]]++;
			q.push((node){a[i].r,b2[0]});
		}
		else
		{
			x=q.top().t;
			b2[x]++;
			q.pop();
			q.push((node){a[i].r,x});
		}
	}
	for(int i=2;i<=n2;i++)
	b2[i]+=b2[i-1];
	b1[0]=b2[0]=0;
	for(int i=0;i<=m;i++)
	sum=max(sum,b1[i]+b2[m-i]);
	printf("%d\n",sum);
	return 0;
}

2021/10/26 21:21
加载中...