AtCoder Regular Contest 037 C: 億マス計算 (二分探索)

問題

C: 億マス計算 - AtCoder Regular Contest 037 | AtCoder

解法

各a[i]の段のmid以下のa*bの数をカウントし、それがKとなるようにmidを二分探索する。

コード

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

public class Main {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		long[] a = new long[N];
		for (int i = 0; i < a.length; i++) {
			a[i] = sc.nextInt();
		}
		long[] b = new long[N];
		for (int i = 0; i < b.length; i++) {
			b[i] = sc.nextInt();
		}
		sc.close();

		Arrays.sort(a);
		Arrays.sort(b);

		long low = 0;
		long high = Long.MAX_VALUE;

		while (high - low > 1) {
			long mid = (low + high) / 2;

			int count = 0;
			int index = N;// a[i]の段におけるmidより小さいa*bの数
			for (int i = 0; i < N; i++) {
				while (index > 0 && a[i] * b[index - 1] > mid) {
					index--;
				}
				count += index;
			}

			if (count >= K) {
				high = mid;
			} else {
				low = mid;
			}
		}
		System.out.println(high);
	}

}