3104-Drying

問題（外部リンク）

3104 -- Drying

実装の概要

最大値を最小化する問題です。二分探索を利用して解を絞り込みます。
「x分で全ての洗濯物を乾燥させられるか」についてですが、直感的には最も時間がかかる洗濯物を毎分ごとに選んで乾燥機を使えばできそうですが毎回ソートをしていたら間に合いません。
重要なこととして、どの洗濯物もx分経てばその分だけは自然乾燥できます。それでも乾かなかった洗濯物についてはそれぞれ回乾燥機を使う必要があります。この判定はでできます。kではなく(k - 1)としているのは、乾燥機使用中は自然乾燥は無視されるためです。
なお、テストケースに存在するかは不明ですが仕様上はk=1もあり得るのでそれは別の処理にします（自然乾燥しかしないのと同じ考え方です）。

public class Main {

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

		int n = Integer.parseInt(br.readLine());
		int time[] = new int[n];

		String tmpArray[] = br.readLine().split(" ");
		for(int i = 0; i < n; i++){
			time[i] = Integer.parseInt(tmpArray[i]);
		}

		int k = Integer.parseInt(br.readLine());

		System.out.println(solve(time, k));
	}

	static int solve(int time[], int k){
		int n = time.length;

		Arrays.sort(time);

		int left = 0;
		int right = 1000000001;

		//解を仮定して二分探索
		while(right - left > 1){
			int mid = (left + right)/2;

			if(check(time, k, mid)){
				right = mid;
			}
			else {
				left = mid;
			}
		}

		return right;
	}

	//limit以内の時間で全て乾かせるか
	static boolean check(int time[], int k, int limit){
		int n = time.length;

		//k == 1のときはつまり自然乾燥と同じ
		if(k == 1){
			for(int i = n - 1; i >= 0 ; i--){
				if(time[i] > limit){
					return false;
				}
			}
			return true;
		}
		int tmpSum = 0;
		for(int i = n - 1; i >= 0; i--){
			//乾燥機を使わなくても乾く場合
			if(time[i] <= limit){
				break;
			}

			//乾燥機を使う必要がある時間を加算
			tmpSum += Math.ceil((double)(time[i] - limit)/(k - 1));

			if(tmpSum > limit){
				return false;
			}
		}

		return true;
	}

}