1654

랜선 자르기 : https://www.acmicpc.net/problem/1654

 

전형적인 바이너리 서치 문제

 

탐색하려는 범위를 랜선의 길이로 잡고, lt 및 rt를 적당한 값의 범위로 선택한다.

그리고 이진 탐색으로 최적값만 구하면 끝.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static int N, K;
	static long[] arr;
	static boolean DBG = false;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		K = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		arr = new long[K];
		for (int i = 0; i < K; i++)
			arr[i] = Integer.parseInt(br.readLine());

		long rt = Arrays.stream(arr).max().getAsLong();
		long lt = 1;
		long answer = 0;
		while (lt <= rt) {
			long mid = (rt + lt) / 2;
			long cnt = check(arr, mid);
			if (cnt >= N) {
				answer = Math.max(mid, answer);
				lt = mid + 1;
			} else {
				rt = mid - 1;
			}
		}
		System.out.println(answer);
	}

	private static long check(long[] list, long length) {
		long cnt = 0;
		for (int i = 0; i < list.length; i++) {
			cnt += list[i] / length;
		}
		return cnt;
	}

}
ex)
4 11
802
743
457
539

200