社区讨论

60 分,后面几个点都re了,求调

P1803凌乱的yyy / 线段覆盖参与者 5已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@lo1haofj
此快照首次捕获于
2023/10/22 21:02
2 年前
此快照最后确认于
2023/11/02 21:36
2 年前
查看原帖
CPP
#include<cstdio> 
#include<algorithm>
using namespace std;
int n;
struct part{
	int a,b;
} x[200000];

part tmp;
int ans=1;

bool cmp(part x,part y)
{
	if(x.b==y.b) return x.a<y.a;
	else return x.b<y.b;
}

void search(int t)
{
	if(t==n) 
	{
		ans++;
		return;
	}
	else
	{
		for(int i=t+1;i<=n;i++)	
		{
			if(x[i].a>=tmp.b)
	    	{
				ans++;
				tmp.a=x[i].a;
				tmp.b=x[i].b;
				search(i);
				return;
			}
		}	
	
	}
}



int main()	
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) 
	{
		scanf("%d%d",&x[i].a,&x[i].b);
	}
	
	sort(x+1,x+n+1,cmp);
	
	tmp.a=x[1].a;
	tmp.b=x[1].b;
	
	search(1);
	printf("%d",ans);
	
	return 0;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...