AtCoder Beginner Contest 023 D: 収集王(二分探索)
解法
二分探索でスコアを探索する。
コード
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); } }