나무 자르기 2805

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

시간복잡도 최악의 경우 나무를 자를수 있는 범위는 0~20억 이므로 이분탐색시 최대 31회 자르게 된다. 나무들의 개수는 최대 100만개이다

20억을 2로 나눈 횟수 X 100만
log(20억) 30.897 X 100만
약 3천만.

log(M) x N

while문의 종료조건이 어려웠다
언제 종료해야할지가 어려웠다

M 이랑 cut(자른나무의 양) 이 일치하는경우
일치 하지 않는 경우를 예외처리하는부분도 헷갈렸다

import java.io.*;
import java.util.*;

public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        Integer[] arrTree = new Integer[N];

        input = br.readLine().split(" ");
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < N; ++i)
        {
            arrTree[i] = Integer.parseInt(input[i]);
            max = Math.max(max, arrTree[i]);
        }

        Arrays.sort(arrTree, Collections.reverseOrder());

        long low = 0;
        long high = max;
        long cut;
        long result;
        while((high - low) > 1)//차이가 1 (포함)이하 일경우 나간다
        {
            result = 0;
            cut = (low+high) / 2;

            for(int i = 0; i < N; ++i)
            {
                if(arrTree[i] > cut)
                    result += arrTree[i] - cut;
                else
                    break;
            }
            if(result > M)
            {
                low = cut;
            }
            else if(result < M)
            {
                high = cut;
            }
            else
            {
                low = cut;
                high = cut;
            }
        }

        System.out.println(low);
    }
}