三分+优先队列 75分求调
查看原帖
三分+优先队列 75分求调
1227383
MPLN楼主2024/10/3 12:08
#include<bits/stdc++.h>
using namespace std;
int n,m1,m2;
struct node{
    int s,e;
}gn[100010],gj[100010];
bool cmp(node x,node y){return x.s<y.s;}
int chk(int x){
    priority_queue<int,vector<int>,greater<int> > pqa,pqb;//优先队列先出更早离开的
    int cnt=0;//有多少不能用的
    for(int i=1;i<=m1;i++){
        while(!pqa.empty()&&pqa.top()<=gn[i].s) pqa.pop();//出掉已经离开的
        if(pqa.size()+1>x) cnt++;//不能用
        else pqa.push(gn[i].e);//可以用
    }
    for(int i=1;i<=m2;i++){
        while(!pqb.empty()&&pqb.top()<=gj[i].s) pqb.pop();
        if(pqb.size()+1>n-x) cnt++;
        else pqb.push(gj[i].e);
    }
    return m1+m2-cnt;
}
int main(){
    cin>>n>>m1>>m2;
    for(int i=1;i<=m1;i++){
        cin>>gn[i].s>>gn[i].e;
    }
    for(int i=1;i<=m2;i++){
        cin>>gj[i].s>>gj[i].e;
    }
  	//按到来时间排序
    sort(gn+1,gn+m1+1,cmp);
    sort(gj+1,gj+m2+1,cmp);
    //三分
    int l=0,r=n;
    while(l<r){
        int lm=l+(r-l)/3;
        int rm=r-(r-l)/3;
        if(chk(lm)<chk(rm)) l=lm+1;
        else r=rm-1;
    }
    cout<<max(chk(l),chk(r));
    return 0;
}
2024/10/3 12:08
加载中...