통나무 수확
골드 V의견: 0
숲속 마을의 나무꾼 오준은 \(N\)그루의 나무를 수확하려 한다. \(i\)번 나무의 높이는 \(H_i\)이다.
나무꾼은 절단기를 이용해 모든 나무를 동일한 정수 높이 \(X\)에서 자른다. \(H_i > X\)인 나무는 \(H_i - X\) 만큼의 목재를 얻고, \(H_i \le X\)인 나무는 잘리지 않는다.
수집해야 하는 목재의 총량이 최소 \(M\)일 때, 목재를 \(M\) 이상 얻을 수 있는 절단 높이 \(X\)의 최댓값을 구하여라.
입력으로 주어지는 \(H_i\)들의 합이 \(M\) 이상임이 항상 보장되므로, 답은 항상 존재한다.
- \(1 \le N \le 200\,000\)
- \(1 \le M \le \sum_{i=1}^{N} H_i\)
- \(1 \le H_i \le 10^9\)
- \(\sum H_i \ge M\) (답은 항상 존재한다)
첫째 줄에 나무의 수 \(N\)과 필요한 목재 총량 \(M\)이 공백으로 구분되어 주어진다.
둘째 줄에 \(N\)개 나무의 높이 \(H_1, H_2, \dots, H_N\)이 공백으로 구분되어 주어진다.
목재를 \(M\) 이상 얻을 수 있는 절단 높이의 최댓값을 출력한다.
4 7
20 15 10 17
15
절단 높이 \(X = 15\)이면 수집량은 \((20-15)+(17-15)=7\)로 조건을 만족한다. \(X = 16\)이면 \((20-16)+(17-16)=5 < 7\)이므로 답은 \(15\)이다.
5 3
1 2 3 4 5
3
\(X = 3\)이면 \((4-3)+(5-3)=3 \ge 3\). \(X = 4\)이면 \((5-4)=1 < 3\). 답은 \(3\).
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
통나무 수확
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
통나무 수확