社区讨论
90分求助,WA#9、#15
P7913[CSP-S 2021] 廊桥分配参与者 3已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @lo7mbvcy
- 此快照首次捕获于
- 2023/10/27 04:09 2 年前
- 此快照最后确认于
- 2023/10/27 04:09 2 年前
c++
CPP#include<bits/stdc++.h>
using namespace std;
int n,m1,m2,text;
int ans1[100005],ans2[100005],ans;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
priority_queue<int,vector<int>,greater<int> >q1;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >p;
priority_queue<int,vector<int>,greater<int> >p1;
struct m{
int land,leave;
}a[100005],b[100005];
int num1=1,num2=1;
bool cmp(m f,m s){
return f.land<s.land;
}
int main(){
cin>>n>>m1>>m2;
for(int i=1;i<=m1;i++){
cin>>a[i].land>>a[i].leave;
}
sort(a+1,a+m1+1,cmp);
for(int i=1;i<=m1;i++){
if(q.size()==0 and i==1){
ans1[num1]++;
text=num1;
num1++;
}else{
while(q.top().first<a[i].land and q.size()){
int o=q.top().second;
q1.push(o);
q.pop();
}
if(q1.size()==0){
text=num1;
ans1[text]++;
num1++;
}else{
text=q1.top();
q1.pop();
ans1[text]++;
}
}
q.push(make_pair(a[i].leave,text));
}
for(int i=1;i<=num1;i++)ans1[i]+=ans1[i-1];
for(int i=1;i<=m2;i++){
cin>>b[i].land>>b[i].leave;
}
sort(b+1,b+m2+1,cmp);
for(int i=1;i<=m2;i++){
if(p.size()==0 and i==1){
ans2[num2]++;
text=num2;
num2++;
}else{
while(p.top().first<b[i].land and p.size()){
int o=p.top().second;
p1.push(o);
p.pop();
}
if(p1.size()==0){
text=num2;
ans2[text]++;
num2++;
}else{
text=p1.top();
p1.pop();
ans2[text]++;
}
}
p.push(make_pair(b[i].leave,text));
}
for(int i=1;i<=num2;i++)ans2[i]+=ans2[i-1];
for(int i=0;i<=n;i++){
ans=max(ans1[i]+ans2[n-i],ans);
}
cout<<ans;
/*cout<<endl;
for(int i=0;i<=n;i++){
cout<<ans1[i]<<" "<<ans2[n-i]<<endl;
}*/
return 0;
}
回复
共 5 条回复,欢迎继续交流。
正在加载回复...