(자바)백준 17179호 컷케익

이것은 이진 검색 문제입니다.


우리는 케이크를 자르고 가장 작은 조각의 최대 길이를 찾아야 합니다.

이진 검색에서 가장 먼저 생각해야 할 것은 검색 기준입니다.


케이크를 자를 때의 길이를 기준으로 합니다.

왼쪽에서 0, 오른쪽에서 l(번의 길이)을 찾습니다.


가운데의 길이를 기준으로 케이크를 자르고 몇 번 자르는지 확인합니다.


Q보다 적게 절단하는 경우 Q까지 절단해야 하므로 중앙으로 오른쪽으로 이동합니다.


Q보다 크거나 같게 자르면 중간 값을 만들 수 있으므로 왼쪽 값을 가운데로 이동하십시오.
위의 과정을 반복하여 최대 길이를 찾습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public static void main(String() args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int ans = 0;
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int l = Integer.parseInt(st.nextToken());
		int() arr = new int(m + 1);

		for (int i = 0; i < m; ++i) {
			arr(i) = Integer.parseInt(br.readLine());
		}
		arr(m) = l;

		for (int i = 0; i < n; ++i) {
			int num = Integer.parseInt(br.readLine());
			int left = 0;
			int right = l;
			while (left <= right) {
				int cnt = 0;
				int prev = 0;
				int mid = (left + right) / 2;
				for (int j = 0; j <= m; ++j) {
					if (arr(j) - prev >= mid) {
						++cnt;
						prev = arr(j);
					}
				}
				if (cnt > num) {
					left = mid + 1;
					ans = Math.max(ans, mid);
				} else {
					right = mid - 1;
				}
			}
			bw.write(right + "\n");
		}
		bw.close();
	}
}