나무 자르기
실버 II의견: 0
나무 \(N\)그루가 서 있다. 절단기의 높이 \(H\)를 정하면, 높이가 \(H\)보다 큰 나무는 윗부분이 잘려 나가고(\(h_i - H\)만큼 얻는다), \(H\) 이하인 나무는 잘리지 않는다.
적어도 \(M\)미터의 나무를 얻으면서 설정할 수 있는 절단기 높이 \(H\)의 최댓값을 구하여라. \(H\)는 음이 아닌 정수이다.
\(1 \le N \le 100\,000\), \(1 \le M \le 2 \times 10^9\), \(1 \le h_i \le 10^9\). 항상 \(M\)미터 이상을 얻을 수 있는 경우만 입력으로 주어진다.
첫째 줄에 나무의 수 \(N\)과 필요한 나무 길이 \(M\)이 주어진다.
둘째 줄에 각 나무의 높이 \(h_i\)가 공백으로 구분되어 주어진다.
조건을 만족하는 절단기 높이의 최댓값을 출력한다.
4 7
20 15 10 17
15
높이 \(15\)로 자르면 \(5 + 0 + 0 + 2 = 7\)미터를 얻는다.
5 20
4 42 40 26 46
36
높이 \(36\)으로 자르면 \(6 + 4 + 10 = 20\)미터를 얻는다.
골드 IV
실버 III막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
나무 자르기
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
나무 자르기