AtCoder Beginner Contest 023 D: 収集王（二分探索）

問題

abc023.contest.atcoder.jp

解法

二分探索でスコアを探索する。

コード

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

public class Main {

    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);

	int N = sc.nextInt();
	long[] H = new long[N];
	long[] S = new long[N];
	for (int i = 0; i < N; i++) {
	    H[i] = sc.nextLong();
	    S[i] = sc.nextLong();
	}
	sc.close();

	long low = 0;
	long high = Long.MAX_VALUE / 2;
	loop: while (high - low > 1) {
	    long mid = (high + low) / 2;
	    long[] seconds = new long[N];
	    for (int i = 0; i < seconds.length; i++) {
		if (mid < H[i]) {
		    low = mid;
		    continue loop;
		} else {
		    seconds[i] = mid - H[i];
		    seconds[i] /= S[i];
		}
	    }
	    Arrays.sort(seconds);

	    boolean isOK = true;
	    for (int i = 0; i < seconds.length; i++) {
		if (seconds[i] < i) {
		    isOK = false;
		    break;
		}
	    }
	    if (isOK) {
		high = mid;
	    } else {
		low = mid;
	    }
	}
	System.out.println(high);

    }

}