BOJ 19700 - 수업

BOJ 19700 - 수업

$h$가 높은 순서대로 보자.

$h$가 젤 높으면 아무곳에나 있어도 상관이 없다.

이제 상관있는건 $k_i$ 값들이다.

각 그룹의 개수를 multiset 으로 관리하며 $k_i-1$ 이하의 가장 큰 것에 현재 학생을 넣는것이 최적이다.

그렇게 함으로써 $k_i$ 가 더작은 학생이 나왔을 때 아직 남은 적은 학생 수가 있는 그룹에 넣어줄 수 있기 때문이다.

엄밀한 증명은 하지않고 풀었다.

void solve() {
   multiset<int> s;
   int n;
   cin >> n;
   vector<pi> a(n);
   for (auto &[h, k]: a) cin >> h >> k;
   sort(all(a), [&](auto &a, auto &b) { return a.fi > b.fi; });
   for (int i = 0; i < n; i++) {
      auto it = s.upper_bound(a[i].se - 1);
      if (it == s.begin()) {
         s.insert(1);
         continue;
      }
      it--;
      int val = *it;
      s.erase(it);
      s.insert(val + 1);
   }
   cout << sz(s);
}