나무 자르기
면접 대비시간 제한1초메모리 제한256 MB
나무들을 높이 H에서 잘라 모은 목재 총합이 M 이상이 되도록 하는 최대 H를 이분 탐색으로 구합니다.
문제
나무 N그루가 한 줄로 서 있고, 집으로 가져갈 나무 길이의 합이 적어도 M미터가 되어야 한다.
목재 절단기의 높이를 H로 설정하면 높이가 H보다 큰 나무는 H 위의 부분만 잘리고, 높이가 H 이하인 나무는 잘리지 않는다. H는 0 이상의 정수로 설정할 수 있다.
필요한 나무를 확보하면서도 나무를 가능한 많이 남기도록, 설정할 수 있는 H의 최댓값을 구하라.
입력
첫째 줄에 나무의 수 N과 필요한 나무 길이 M이 주어진다.
- 1 <= N <= 1,000,000
- 1 <= M <= 2,000,000,000
둘째 줄에 나무 N그루의 높이가 주어진다. 각 높이는 0 이상 1,000,000,000 이하의 정수이다. 모든 나무 높이의 합은 항상 M 이상이다.
출력
적어도 M미터의 나무를 얻을 수 있도록 하는 절단기 높이 H의 최댓값을 출력한다.