나무 자르기 (매개변수 탐색)

문제

나무 $N$ 그루의 길이 $L_0, L_1, \ldots, L_{N-1}$ 이 주어진다. 톱의 높이 $H$ 를 정수로 설정하면, $L_i > H$ 인 나무는 $L_i - H$ 만큼 잘려 나오고, $L_i \le H$ 인 나무는 아무것도 안 잘린다.

적어도 $M$ 미터 이상의 나무를 얻을 수 있는 가장 큰 정수 $H$ 를 구하라.

매개변수 탐색

$H$ 를 0부터 $\max L_i$ 까지 모두 시도해 보면 $H$ 의 범위가 $10^9$ 까지 갈 수 있어 시간 안에 못 푼다.

관찰: $H$ 가 커질수록 얻는 양이 단조롭게 줄어든다. 그러면 "이 $H$ 로 $M$ 이상을 얻을 수 있나?"라는 결정 함수가 단조롭다. 답에 이진 탐색을 걸자.

int can(long long H) {
  long long total = 0;
  for (int i = 0; i < N; i++) {
    if (L[i] > H) total += L[i] - H;
    if (total >= M) return 1;  // 빨리 종료
  }
  return total >= M;
}

// 이진 탐색
long long lo = 0, hi = max_L;
long long ans = 0;
while (lo <= hi) {
  long long mid = lo + (hi - lo) / 2;
  if (can(mid)) { ans = mid; lo = mid + 1; }
  else            hi = mid - 1;
}

검사가 $O(N)$ 이고 이진 탐색이 $O(\log H)$ 이라 전체 $O(N \log H)$ .

입력

첫째 줄에 두 정수 $N, M$ 이 공백으로 구분되어 주어진다.

둘째 줄에 $N$ 개의 정수 $L_0, L_1, \ldots, L_{N-1}$ 이 공백으로 구분되어 주어진다.

출력

$M$ 미터 이상을 얻을 수 있는 가장 큰 정수 $H$ 를 출력한다.

제한

$1 \le N \le 10^6$
$1 \le M \le 2 \cdot 10^9$

나무 자르기 (매개변수 탐색)

나무 자르기 (매개변수 탐색)

문제

매개변수 탐색

제한

입출력 예시