20pts求看一下咋回事
查看原帖
20pts求看一下咋回事
950268
Luban_No_7楼主2023/3/20 12:59

看看我思路对不对

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > N, I;
vector<int> timesN, timesI;
set<pair<int, int> > bn, bi;
vector<int> resN, resI;
bool cmp(pair<int, int> a, pair<int, int> b){
    if(a.first == b.first) return a.second < b.second;
    return a.first < b.first;
}
int main(){
    int n, m1, m2;
    scanf("%d %d %d", &n, &m1, &m2);
    N.resize(m1 + m2), I.resize(m1 + m2);
    timesN.resize(m1 + m2), timesI.resize(m1 + m2);
    resN.resize(m1 + m2), resI.resize(m1 + m2);
    for(int i = 0; i < m1; i++) scanf("%d %d", &N[i].first, &N[i].second);
    for(int i = 0; i < m2; i++) scanf("%d %d", &I[i].first, &I[i].second);
    sort(N.begin(), N.begin() + m1, cmp), sort(I.begin(), I.begin() + m2, cmp);
    for(int i = 0, cnt = 0; i < m1; i++){
        auto it = bn.lower_bound(make_pair(N[i].first, 0));
        if(it != bn.begin()) it--, timesN[i] = it->second, bn.erase(it);
        else timesN[i] = ++cnt;
        bn.insert(make_pair(N[i].second, timesN[i]));
        resN[timesN[i]]++;
    }
    for(int i = 0, cnt = 0; i < m2; i++){
        auto it = bi.lower_bound(make_pair(I[i].first, 0));
        if(it != bi.begin()) it--, timesI[i] = it->second, bi.erase(it);
        else timesI[i] = ++cnt;
        bi.insert(make_pair(I[i].second, timesI[i]));
        resI[timesI[i]]++;
    }
    partial_sum(resN.begin(), resN.end(), resN.begin());
    partial_sum(resI.begin(), resI.end(), resI.begin());
    int ans = 0;
    for(int i = 0; i <= min(n, m1); i++){
        ans = max(resN[i] + resI[n - i], ans);
    }
    printf("%d\n", ans);
    return 0;
}
2023/3/20 12:59
加载中...