20pts 求调 求求求求求求 看看思路有什么问题吗
查看原帖
20pts 求调 求求求求求求 看看思路有什么问题吗
516894
skkkkkkkkkk楼主2024/10/18 19:21
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m1,m2;
int cnt1=0,cnt2=0;
bool flg1[N],flg2[N];
int id1[N],id2[N];
struct Node{
    int arr,lea,id;
    bool operator < (const Node &a){
        return arr<a.arr;
    }
}a[N],b[N];
bool cmp(int a, int b){return a>b;}

void nxta(int x){//找第一架降落时间晚于a[x].lea的飞机
    if(x>m1)return;
    flg1[x]=1;
    int l=x+1,r=m1,res=-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid].arr>a[x].lea&&flg1[mid]==0){
            res=mid;
            r=mid-1;
        }else l=mid+1;
    }
    if(res==-1)return;
    id1[cnt1]++;
    nxta(res);
}
void nxtb(int x){
    if(x>m2)return;
    flg2[x]=1;
    int l=x+1,r=m2,res=-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid].arr>a[x].lea&&flg2[mid]==0){
            res=mid;
            r=mid-1;
        }else l=mid+1;
    }
    if(res==-1)return;
    id2[cnt2]++;
    nxtb(res);
}

int main(){
    cin>>n>>m1>>m2;
    for(int i=1;i<=m1;i++){
        cin>>a[i].arr>>a[i].lea;
    }
    for(int i=1;i<=m2;i++){
        cin>>b[i].arr>>b[i].lea;
    }
    sort(a + 1,a + m1 + 1);
    sort(b + 1,b + m2 + 1);
    
    for(int i=1;i<=m1;i++){
        if(flg1[i]==0){
            cnt1++;
            id1[cnt1]=1;
            nxta(i);
        }
        if(cnt1>n)break;
    }
    for(int i=2;i<=cnt1;i++){
        id1[i]=id1[i-1]+id1[i];
    }
    for(int i=cnt1+1;i<=n;i++){
        id1[i]=id1[cnt1];
    }
    for(int i=1;i<=m2;i++){
        if(flg2[i]==0){
            cnt2++;
            id2[cnt2]=1;
            nxtb(i);
        }
        if(cnt2>n)break;
    }
    for(int i=2;i<=cnt2;i++){
        id2[i]=id2[i-1]+id2[i];
    }
    for(int i=cnt2+1;i<=n;i++){
        id2[i]=id2[cnt2];
    }
    
    int ans=-1;
    for(int i=0;i<=n;i++){
        ans=max(id1[i]+id2[n-i],ans);
    }
    printf("%d",ans);
    return 0;
}
2024/10/18 19:21
加载中...