2831번: PLES

https://www.acmicpc.net/problem/2831

$O(n\lg n)$

각 큰 키를 요구하는 사람에 대해 해당 사람과 춤을 출 수 있는 사람 중 가장 작은 키의 사람과 매칭시킨다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n, r;
vector<pair<int, int> > p[2];
int main() {
    scanf("%d", &n);
    for (int i = 0, x; i < n; i++) {
        scanf("%d", &x);
        x < 0 ? p[1].push_back({ -x,0 }) : p[0].push_back({ x,1 });
    }
    for (int i = 0, x; i < n; i++) {
        scanf("%d", &x);
        x < 0 ? p[0].push_back({ -x,0 }) : p[1].push_back({ x,1 });
    }
    sort(p[0].begin(), p[0].end());
    sort(p[1].begin(), p[1].end());
    for (int i = 0; i < 2; i++) {
        int c = 0;
        for (auto it : p[i]) {
            if (it.second) c++;
            else if (c) c--, r++;
        }
    }
    printf("%d", r);
    return 0;
}