社区讨论
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 条回复,欢迎继续交流。
正在加载回复...