是数据水了还是我复杂度没算对?n^2暴力居然能AC!
查看原帖
是数据水了还是我复杂度没算对?n^2暴力居然能AC!
191846
WhiteSunFlower楼主2021/10/24 10:02
#include<bits/stdc++.h>
using namespace std;
const int N=100616;
int n,m1,m2,ans;
int k1[N],k2[N],o1[N],o2[N];
struct Node{
    int a,b;
}s1[N],s2[N];
bool cmp(Node a,Node b){
    return a.a<b.a;
}
void c1(){
    int cmp;
    memset(k1,0,sizeof(k1));
    for(int i=1;i<=m1;i++){
        cmp=1;
        while(k1[cmp]>s1[i].a)cmp++;
        k1[cmp]=s1[i].b,o1[cmp]++;//数组o[i]指有几架飞机停在第i座廊桥 
    }
    for(int i=1;i<=n;i++)o1[i]+=o1[i-1];//前缀和就可以算出有i座廊桥时可以满足几个飞机的需求 
    return;
}
void c2(){
    int cmp;
    memset(k2,0,sizeof(k2));
    for(int i=1;i<=m2;i++){
        cmp=1;
        while(k2[cmp]>s2[i].a)
            cmp++;
        k2[cmp]=s2[i].b,o2[cmp]++;
    }
    for(int i=1;i<=n;i++)o2[i]+=o2[i-1];
    return;
}
int main(){
//    freopen("airport.in","r",stdin);
//    freopen("airport.out","w",stdout);
    cin >> n >> m1 >> m2;
    for(int i=1;i<=m1;i++)cin >> s1[i].a >> s1[i].b;
    for(int i=1;i<=m2;i++)cin >> s2[i].a >> s2[i].b;
    sort(s1+1,s1+1+m1,cmp);
    sort(s2+1,s2+1+m2,cmp);
    c1();c2();
    for(int i=0;i<=n;i++)ans=max(ans,o1[i]+o2[n-i]);
    cout << ans << endl;
    return 0;
}
2021/10/24 10:02
加载中...