廊桥95分求调
  • 板块题目总版
  • 楼主baiyh
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/11/26 22:30
  • 上次更新2023/11/27 13:56:26
查看原帖
廊桥95分求调
822746
baiyh楼主2023/11/26 22:30
#include<bits/stdc++.h>
using namespace std;
int n,m1,m2;
typedef pair<int,int> pii;
pii a[100005],b[100005];
int ans1[100005],ans2[100005];
void solve(pii a[],int m,int ans[]){
    priority_queue<int,vector<int>,greater<int>> p1;
    priority_queue<pii,vector<pii>,greater<pii>> p2;
    for(int i=1;i<=n;i++) p1.push(i);
    for(int i=1;i<=m;i++){
        while(!p2.empty()&&a[i].first>p2.top().first){
            p1.push(p2.top().second);
            p2.pop();
        }
        if(!p1.empty()){
            p2.push((pii){a[i].second,p1.top()});
            ans[p1.top()]++;
            p1.pop();
        }
    }
    for(int i=1;i<=n;i++)ans[i]+=ans[i-1];
}
int main(){
    scanf("%d%d%d",&n,&m1,&m2);
    for(int i=1;i<=m1;i++) scanf("%d%d",&a[i].first,&a[i].second);
    for(int i=1;i<=m2;i++) scanf("%d%d",&b[i].first,&b[i].second);
    sort(a+1,a+1+m1);
    sort(b+1,b+1+m2);
    solve(a,m1,ans1);
    solve(b,m2,ans2);
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,ans1[i]+ans2[n-i]);
    }
    printf("%d",ans);
	return 0;
}
2023/11/26 22:30
加载中...