【水】一个疑问
  • 板块灌水区
  • 楼主AllenKING_RED
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/11/1 23:10
  • 上次更新2023/11/4 01:35:59
查看原帖
【水】一个疑问
228745
AllenKING_RED楼主2021/11/1 23:10

为什么这两个代码中的前一个会卡住

#include<bits/stdc++.h>
using namespace std;
int n,m1,m2;
priority_queue<pair<int,int >,vector<pair<int,int> >,greater<pair<int,int> > >a;
priority_queue<int,vector<int>,greater<int> >b;
struct plane{
	int st;
	int ed;
}f[100050];
bool cmp(plane a,plane b)
{
	return a.st<b.st;
}
int ans1[100050],ans2[100050];
int main(void)
{
	cin>>n>>m1>>m2;
	for(int i=1;i<=m1;i++)
		cin>>f[i].st>>f[i].ed;
	for(int i=1;i<=n;i++)
		b.push(i);
	sort(f+1,f+m1+1,cmp);

	for(int i=1;i<=m1;i++)
	{
		while(a.top().first<f[i].st&&!a.empty())
		{
			b.push(a.top().second);
			a.pop();
		}
		if(!b.empty())
		{
			a.push(make_pair(f[i].ed,b.top()));
			ans1[b.top()]++;
			b.pop();
		}
	}
	for(int i=1;i<=n;i++)ans1[i]+=ans1[i-1];
	while(!a.empty())a.pop();
	while(!b.empty())b.pop();
	for(int i=1;i<=m2;i++)
		cin>>f[i].st>>f[i].ed;
	sort(f+1,f+m2+1,cmp);
	for(int i=1;i<=n;i++)b.push(i);
	for(int i=1;i<=m2;i++)
	{
		while(a.top().first<f[i].st&&!a.empty())
		{
			b.push(a.top().second);
			a.pop();
		}
		if(!b.empty())
		{
			a.push(make_pair(f[i].ed,b.top()));
			ans2[b.top()]++;
			b.pop();
		}
	}
	for(int i=1;i<=n;i++)ans2[i]+=ans2[i-1];
	int maxx=-2147483647;
	for(int i=0;i<=n;i++)
	maxx=max(maxx,ans1[i]+ans2[n-i]);
	cout<<maxx<<endl;
	return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n,m1,m2;
priority_queue<pair<int,int >,vector<pair<int,int> >,greater<pair<int,int> > >a;
priority_queue<int,vector<int>,greater<int> >b;
struct plane{
	int st;
	int ed;
}f[100050];
bool cmp(plane a,plane b)
{
	return a.st<b.st;
}
int ans1[100050],ans2[100050];
int main(void)
{
	cin>>n>>m1>>m2;
	for(int i=1;i<=m1;i++)
		cin>>f[i].st>>f[i].ed;
	for(int i=1;i<=n;i++)
		b.push(i);
	sort(f+1,f+m1+1,cmp);

	for(int i=1;i<=m1;i++)
	{
		if(!a.empty())
		while(a.top().first<f[i].st)
		{
			b.push(a.top().second);
			a.pop();
			if(a.empty())break;
		}
		if(!b.empty())
		{
			a.push(make_pair(f[i].ed,b.top()));
			ans1[b.top()]++;
			b.pop();
		}
	}
	for(int i=1;i<=n;i++)ans1[i]+=ans1[i-1];
	while(!a.empty())a.pop();
	while(!b.empty())b.pop();
	for(int i=1;i<=m2;i++)
		cin>>f[i].st>>f[i].ed;
	sort(f+1,f+m2+1,cmp);
	for(int i=1;i<=n;i++)b.push(i);
	for(int i=1;i<=m2;i++)
	{
		if(!a.empty())
		while(a.top().first<f[i].st)
		{
			b.push(a.top().second);
			a.pop();
			if(a.empty())break;
		}
		if(!b.empty())
		{
			a.push(make_pair(f[i].ed,b.top()));
			ans2[b.top()]++;
			b.pop();
		}
	}
	for(int i=1;i<=n;i++)ans2[i]+=ans2[i-1];
	int maxx=-2147483647;
	for(int i=0;i<=n;i++)
	maxx=max(maxx,ans1[i]+ans2[n-i]);
	cout<<maxx<<endl;
	return 0;
}

中间关于a.empty()的判断为什么不能放在while里,否则就会有死循环

2021/11/1 23:10
加载中...