8875번: 장난감 정리 로봇

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

$O((a+b+t\lg t)\lg t)$

먼저 1분째 정리가 가능한지 확인하는 그리디 풀이법에 대해 알아보자.

1. X[1...a]를 오름차순 정렬한다.
2. i를 증가시켜가며 무게가 X[i]이하인 장난감들 중 최대 크기인 장난감을 제외한다.
3. 임의의 i에 대해 Y[i]이하인 장난감들 중 최대 크기인 장난감을 제외한다.
4. 남은 장난감이 있다면 불가능, 아니면 가능하다.

c분 이하에 정리가 가능한지 확인하기 위해선 각 로봇들이 c개 있다고 가정하고 위 알고리즘을 적용하면 된다.
즉, 결정문제로 바꿔서 파라메트릭 서치를 이용하면 문제를 해결할 수 있다.

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int a, b, t, x[50000], y[50000];
pair<int, int> p[1000000];
bool f(int c) {
    priority_queue<int> pq;
    int j = 0;
    for (int i = 0; i < a; i++) {
        while (j < t&&p[j].first < x[i]) pq.push(p[j++].second);
        for (int k = c; k--&&!pq.empty();) pq.pop();
    }
    for (; j < t; j++) pq.push(p[j].second);
    for (int i = b; i--&&!pq.empty();) {
        if (pq.top() >= y[i]) return false;
        for (int k = c; k--&&!pq.empty();) pq.pop();
    }
    return pq.empty();
}
int main() {
    scanf("%d%d%d", &a, &b, &t);
    for (int i = 0; i < a; i++) scanf("%d", x + i);
    for (int i = 0; i < b; i++) scanf("%d", y + i);
    for (int i = 0; i < t; i++) scanf("%d%d", &p[i].first, &p[i].second);
    sort(x, x + a);
    sort(y, y + b);
    sort(p, p + t);
    int low = 1, up = t, mid;
    while (low <= up) {
        mid = (low + up) / 2;
        f(mid) ? up = mid - 1 : low = mid + 1;
    }
    printf("%d", low > t ? -1 : low);
    return 0;
}