Codeforces Round #307 Div2 C: GukiZ hates Boxes

問題

codeforces.com

解法

codeforces.com

二分探索で間に合う最小の時間を探す。適当に決めた時間に対して、以下の操作を繰り返す。

• 残ってる人の中から１人を、残っている一番遠い箱まで派遣する。
• その人が時間内に一番遠い箱が片付け終わらないなら、可能な限り片付ける。
• 片付け終わるなら、残った時間でその一つ手前の箱も片付ける。
• それも終わるならまた一つ手前の…と繰り返していく。

こうすることで、時間を決めた時に間に合うかどうか判定できる。

コード

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	private final long MAX_TIME = Long.MAX_VALUE / 2;

	public void solve() {
		Scanner sc = new Scanner(System.in);
		int pileNum = sc.nextInt();
		int persons = sc.nextInt();
		int[] boxes = new int[pileNum];
		for (int i = 0; i < pileNum; i++) {
			boxes[i] = sc.nextInt();
		}
		sc.close();

		// 二分探索
		long high = MAX_TIME;
		long low = 0;
		while (high - low > 1) {
			long time = (high + low) / 2;
			int[] copy = Arrays.copyOf(boxes, pileNum);
			int cur = pileNum - 1;// 今残ってる一番端の箱の位置
			for (int i = 0; i < persons; i++) {
				while (cur >= 0 && copy[cur] == 0) {
					cur--;
				}
				long rest = time;
				rest -= (cur + 1);
				while (rest > 0 && cur >= 0) {
					if (rest >= copy[cur]) {
						// 時間に余裕がある時
						rest -= copy[cur];
						copy[cur] = 0;
						while (cur >= 0 && copy[cur] == 0) {
							cur--;
						}
					} else {
						// 余裕がない時
						copy[cur] -= rest;
						rest = 0;
					}
				}
			}

			// 終わっているかどうか
			if (cur == -1 && copy[0] == 0) {
				high = time;
			} else {
				low = time;
			}
		}

		System.out.println(high);
	}

	public static void main(String[] args) {
		new Main().solve();
	}

}