BOJ 21820 - Acowdemia I

BOJ 21820 - Acowdemia I

이분탐색을 잘 돌려주면 된다.

$c_i$ 를 내림차순 정렬하고 큰것부터 골라가면서 $h$가 가능한지 판별한다.

각 paper당 하나의 citation만 가능하다는 점을 유의하자.

void solve() {
   int N, L;
   cin >> N >> L;
   vi A(N);
   fv(A);
   sort(all(A), greater<>());
   int l = 0, r = N, h = 0;
   while (l <= r) {
      int m = l + r >> 1;
      ll ns = 0;
      for (int i = 0; i < m; i++) {
         int need = max(0, m - A[i]);
         if (need >= 2) {
            ns = 1e9;
            break;
         }
         ns += need;
      }
      if (ns <= L) h = m, l = m + 1;
      else r = m - 1;
   }
   cout << h;
}