BOJ 2792 - 보석 상자

BOJ 2792 - 보석 상자

이게 뭐지하게 만드는 이분 탐색 문제이다.

문제를 잘 읽고 해석해야 한다.

아무도 못받는 아이가 있어도 되므로

$f(M)=$ $M$ 개씩 나눠줄 때 생기는 그룹이 $N$ 이하인가? 를 만족하는 가장 작은 $M$ 을 찾아주면 된다.

계속 작아질수록 그룹이 더 많이생겨서 아이보다 많아지기 때문이다.

void solve() {  
   int n, m;  
   cin >> n >> m;  
   vi a(m);  
   fv(a);  
  
   int L = 1, R = maxe(a), A = -1;  
   while (L <= R) {  
      int M = L + R >> 1;  
      int cnt = 0;  
      for (int i = 0; i < m; i++) {  
         cnt += a[i] / M;  
         if (a[i] % M) cnt++;  
      }  
      if (cnt <= n) {  
         R = M - 1;  
         A = M;  
      } else L = M + 1;  
   }  
   cout << A;  
}