社区讨论

85pt求调

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

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@m2mzmrof
此快照首次捕获于
2024/10/24 15:34
去年
此快照最后确认于
2025/11/04 16:21
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int n,m1,m2,top1,top2,f1[100005],f2[100005],ans=-1;
struct node{
	ll a,b;
}p[100005];
bool cmp(node a,node b){
	return a.a<b.a;
}
priority_queue<ll,vector<ll>,greater<ll>> wait;
priority_queue<int,vector<int>,greater<int>> able;
inline ll get_time(ll x){return x/100000;}
inline int get_id(ll x){return x%100000;}
inline ll make(ll a,int b){return a*100000+b;}
int main(){
	cin>>n;
	cin>>m1>>m2;
	for(int i=0;i<m1;i++)cin>>p[i].a>>p[i].b;
	sort(p,p+m1,cmp);
	for(int i=0;i<m1;i++){
		while(!wait.empty()&&get_time(wait.top())<p[i].a){
			able.push(get_id(wait.top()));
			wait.pop();
		}
		if(able.empty()){
			f1[++top1]++;
			wait.push(make(p[i].b,top1));
			
		}else{
			f1[able.top()]++;
			wait.push(make(p[i].b,able.top()));
			able.pop();
		}
	}
	
	while(!wait.empty())wait.pop();
	while(!able.empty())able.pop();
	
	for(int i=0;i<m2;i++)cin>>p[i].a>>p[i].b;
	sort(p,p+m2,cmp);
	for(int i=0;i<m2;i++){
		while(!wait.empty()&&get_time(wait.top())<p[i].a){
			able.push(get_id(wait.top()));
			wait.pop();
		}
		if(able.empty()){
			f2[++top2]++;
			wait.push(make(p[i].b,top2));
		}else{
			f2[able.top()]++;
			wait.push(make(p[i].b,able.top()));
			able.pop();
		}
	}
	for(int i=1;i<=top1;i++)f1[i]=f1[i]+f1[i-1];
	for(int i=1;i<=top2;i++)f2[i]=f2[i]+f2[i-1];
	for(int i=0;i<=n;i++){
//		cout<<f1[i]+f2[n-i]<<"\n";
		ans=max(ans,f1[i]+f2[n-i]);
	}
	cout<<ans;
}

回复

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

正在加载回复...