[실버 2][2회독] 나무자르기

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

예산 문제와 같다

 

M <= sum을 사용하는 lower_bound는

 

M < sum과

M = sum 이 다른 값을 내뱉는다

 

upper_bound를 사용하여

M < sum을 사용해 마지막 출력을 원하므로 low를 출력해줘야 한다

 

*통나무 길이 합이 double이네

public static int upper_bound(int[] arr, int M) {
    int low = -1;

    int high = 0;
    for (int tmp : arr)
        high = Math.max(high, tmp);
    high += 1;

    while (low + 1 < high) {
        int mid = (low + high) / 2;

        double sum = 0;
        for (int tmp : arr) {
            if (tmp - mid > 0)
                sum += tmp - mid;
        }

        if (M < sum)
            low = mid;
        else if (M == sum)
            low = mid;
        else
            high = mid;
    }

    return low;
}