社区讨论

50求调

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

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@m1soqyph
此快照首次捕获于
2024/10/03 10:36
去年
此快照最后确认于
2025/11/04 18:14
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int ans1[maxn],ans2[maxn];
bool flag1[maxn],flag2[maxn];
int flag1_num,flag2_num;
int sum1[maxn],sum2[maxn];
struct plant {
	int reach;
	int leave;
}a1[maxn],a2[maxn];
bool cmp(plant a,plant b){
	return a.reach<b.reach;
}
int main(){
	int n,m1,m2,num1=0,num2=0;
	cin>>n>>m1>>m2;
	for(int i=1;i<=m1;i++)cin>>a1[i].reach>>a1[i].leave;
	for(int i=1;i<=m2;i++)cin>>a2[i].reach>>a2[i].leave;
	sort(a1+1,a1+1+m1,cmp);
	sort(a2+1,a2+1+m2,cmp);
	//for(int i=1;i<=m2;i++)cout<<a2[i].reach<<" "<<a2[i].leave<<endl;
	while(flag1_num<m1){
		num1++;
		int j=0;
		while(flag1[j]==1)j++;
		for(int i=j+1,last=j;i<=m1;i++){
			if(a1[last].leave<a1[i].reach&&flag1[i]!=1){
				ans1[num1]++;
				flag1_num++;
				last=i;
				flag1[i]=1;
			}
		}
		sum1[num1]=sum1[num1-1]+ans1[num1];
	}
	while(flag2_num<m2){
		num2++;
		int j=0;
		while(flag2[j]==1)j++;
		for(int i=j+1,last=j;i<=m2;i++){
			if(a2[last].leave<a2[i].reach&&flag2[i]!=1){
				ans2[num2]++;
				flag2_num++;
				last=i;
				flag2[i]=1;
			}
		}
		sum2[num2]=sum2[num2-1]+ans2[num2];
	}
	num2++;
	sum2[num2]=sum2[num2-1]+ans2[num2];
	//for(int i=1;i<=num2;i++)cout<<" "<<sum2[i]<<endl;
	int answer=-858516,num3=1;
	int jishu1,jishu2;
	if(num1>=n)jishu1=n,jishu2=0;
	else if(num1<n)jishu1=num1,jishu2=n-num1;
	while(num3<=n+1){
		answer=max(answer,sum1[jishu1]+sum2[jishu2]);
		jishu1--;
		jishu2++;
		num3++;
	}
	cout<<answer;
	return 0;
}

回复

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

正在加载回复...