BOJ 19700 수업

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

19700번: 수업

 

이진검색트리(multiset)을 이용해서 푼 문제입니다.

이진검색트리에 삽입되는 원소는 각 팀의 인원 수 입니다. 즉, 현재 각 팀에 있는 사람의 구체적인 키를 저장하지 않아도 문제를 해결할 수 있습니다.

 

그 이유는, 키가 가장 큰 사람부터 팀 배정을 하면 되기 때문입니다.

그렇게 한다면, 현재 키가 K번째로 큰 사람의 팀을 배정해야 한다고 할 때, 현재 존재하는 모든 팀에 소속된 모든 사람이 이 사람보다 키가 크다는 것은 자명합니다.

 

이때 이 사람은, 자신이 들어갈 수 있는 팀(자기보다 키가 큰 사람이 h명 미만인 팀. 즉, 팀원의 수가 h명 미만인 팀) 중에 팀원의 수가 가장 많은 팀에 들어가면 됩니다. 즉, 제한을 가장 빡빡하게 맞추는 팀에 들어가는 것입니다(정당성 증명은 과감하게 생략하고 proof by ac).

 

자기가 소속될 팀을 빠르게 찾기 위해 이진검색트리를 이용하고, 팀원의 수가 같은 팀이 여럿 존재할 수 있기 때문에 multiset을 사용해야 합니다. 만약 그런 들어갈 수 있는 팀이 없다면, 자신으로만 구성된 새로운 팀을 만들면 됩니다.

 

 

#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
priority_queue<pii> pq;
multiset<int> ss;


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    for (int i = 0; i < N; i++) {
        int h, k;
        cin >> h >> k;
        pq.push({ h, k });
    }

    while (!pq.empty()) {
        pii cur = pq.top();
        pq.pop();
        int h, k;
        tie(h, k) = cur;
        auto loc = ss.lower_bound(k);

        if (loc == ss.begin()) {
            ss.insert(1);
        }else {
            auto rloc = prev(loc);
            if (*rloc < k) {
                int upd = *rloc + 1;
                ss.erase(rloc);
                ss.insert(upd);
            }else {
                ss.insert(1);
            }
        }
    }

    cout << sz(ss);
}