社区讨论

数据加强警告(doge)

P7913[CSP-S 2021] 廊桥分配参与者 3已保存回复 4

讨论操作

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

当前回复
4 条
当前快照
1 份
快照标识符
@lobgawm3
此快照首次捕获于
2023/10/29 20:32
2 年前
此快照最后确认于
2023/11/04 01:57
2 年前
查看原帖

我这n*m+mlogm+O(n)都能过?

CPP
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define rg register
using namespace std;

int n,m1,m2,ans=-233,cnt;
int ho[100010],ab[100010],f[100010];
struct nod{
	int a,b;
}x1[100010],x2[100010];

bool cmp(nod x,nod y){
	return x.a<y.a;
}

int main()
{
	cin>>n>>m1>>m2;
	for(rg int i=1;i<=m1;i++) scanf("%d %d",&x1[i].a,&x1[i].b);
	for(rg int i=1;i<=m2;i++) scanf("%d %d",&x2[i].a,&x2[i].b);
	
	sort(x1+1,x1+1+m1,cmp); sort(x2+1,x2+1+m2,cmp);
	
	cnt=1; 
	for(rg int i=1;i<=m2;i++)
	 {
	 	rg int k;
	 	for(k=1;k<=cnt;k++)
	 	 if(x2[i].a>=f[k])
	 	  {
	 	  	f[k]=x2[i].b; ab[cnt]++; break;
	 	  }
	 	if(k>cnt) 
		 {
		 	cnt++; ab[cnt]=ab[cnt-1]+1; f[cnt]=x2[i].b;
		 }
		else
		 {
		 	for(int rg j=k;j<=cnt-1;j++) ab[j]++;
		 } 
	 }
	cnt=1; memset(f,0,sizeof(f));
	for(rg int i=1;i<=m1;i++)
	 {
	 	rg int k;
	 	for(k=1;k<=cnt;k++)
	 	 if(x1[i].a>=f[k])
	 	  {
	 	  	f[k]=x1[i].b; ho[cnt]++; break;
	 	  }
	 	if(k>cnt) 
		 {
		 	cnt++; ho[cnt]=ho[cnt-1]+1; f[cnt]=x1[i].b;
		 }
		else
		 {
		 	for(int rg j=k;j<=cnt-1;j++) ho[j]++;
		 } 
	 }
	if(cnt<n)
	 {
	 	for(rg int i=cnt+1;i<=n;i++) ho[i]=ho[cnt];
	 }
	
	for(rg int i=0;i<=n;i++)
	 {
	 	int j=n-i;
	 	ans=max(ans,ho[i]+ab[j]);
	 }
	printf("%d\n",ans);
	
	return 0;
}

回复

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

正在加载回复...