문제
풀이
가장 긴 나무를 right로, 1을 left로 시작하여 이분탐색을 진행하였다. 기존의 이분 탐색과 똑같으며, 다만 mid가 tree의 높이보다 클 때 추가되는 나무의 길이가 없다는 것만 고려해주면 되는 문제이다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <vector>
using namespace std;
int main(){
long long N;
long long M;
scanf("%lld %lld", &N, &M);
long long arr_max = 0;
vector<long long> arr(N);
for(int i = 0; i<N; i++){
scanf("%lld", &arr[i]);
arr_max = max(arr_max, arr[i]);
}
long long left = 1;
long long right = arr_max;
long long result = 0;
while(left<=right){
long long mid = (left+right)/2;
long long tree = 0;
for(int i = 0; i<N; i++){
if(mid >= arr[i]){
continue;
}
else tree += arr[i] - mid;
}
if(tree >= M){
left = mid + 1;
result = max(result, mid);
}
else right = mid - 1;
}
printf("%lld\n", result);
}
