[백준 8875] 장난감 정리 로봇

문제

www.acmicpc.net/problem/8875

 

알고리즘

Greedy

 

풀이

무게와 크기가 있는 장난감 $T$개가 주어집니다. 장난감을 정리하기 위해 연약한 로봇 $A$개와 작은 로봇 $B$개가 주어질 때, 정리하기 위한 최소 시간을 구하는 문제입니다. 연약한 로봇은 장난감의 크기와는 상관없이 자기보다 무게가 덜 나가는 장난감을 정리할 수 있고 작은 로봇은 무게에 상관없이 자기보다 작은 장난감을 정리할 수 있습니다.

 

이분탐색을 통해 정답을 찾아 나가야 합니다. 효율적인 정리를 위해 연약한 로봇은 각자가 처리할 수 있는 장난감들이 있다면 그 중에서도 가장 크기가 큰 장난감들부터 정리해나가면 됩니다. 연약한 로봇의 처리가 끝난 후 작은 로봇들은 정리가 되지 않은 장난감들을 처리해나가는데, 크기가 가장 큰 로봇부터 큰 장난감을 처리하면 됩니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

const int MAXR = 5e4 + 5;
const int MAXT = 1e6 + 5;
typedef pair<int, int> pii;

int a, b, t;
int x[MAXR], y[MAXR];
pii xy[MAXT];

bool solve(int c) {
    priority_queue<int> pq;
    int toy = 0;
    rep(i, a) {
        while (toy < t && xy[toy].first < x[i])
            pq.emplace(xy[toy++].second);
        int sec = c;
        while (sec-- && !pq.empty())
            pq.pop();
    }
    while (toy < t) {
        pq.emplace(xy[toy++].second);
    }
    for (int i = b - 1; i >= 0; --i) {
        int sec = c;
        while (sec--) {
            if (pq.empty())
                return 1;
            if (pq.top() >= y[i])
                return 0;
            pq.pop();
        }
    }
    return pq.empty();
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> a >> b >> t;
    rep(i, a) cin >> x[i];
    rep(i, b) cin >> y[i];
    rep(i, t) cin >> xy[i].first >> xy[i].second;

    sort(x, x + a);
    sort(y, y + b);
    sort(xy, xy + t);

    int lo = 1;
    int hi = t;
    int best = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (solve(mid)) {
            best = mid;
            hi = mid - 1;
        } else
            lo = mid + 1;
    }
    cout << best;
    return 0;
}