Submission #58971

---

Source Code Expand

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

public class Main {

	static Scanner sc = new Scanner(System.in);
	static int N;
	static int[] a, b;
	static long sum;

	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		N = sc.nextInt();
		a = new int[N];
		b = new int[N];
		long max = 0;
		for (int i = 0; i < N; ++i) {
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();
			sum += a[i];
		}
		long ans = 1L << 60;
		for (int i = 0; i < N; ++i) {
			long mv = (long) Math.ceil(1.0 * (b[i] - 1) * sum / a[i]);
			for (long j = mv; j <= mv + a[i]; ++j) {
				if (possible(j)) {
					ans = Math.min(ans, j);
					break;
				}
			}
		}
		//		long ans = max;
		//		for (long i = max; i >= 0 && System.currentTimeMillis() - start < 1900; --i) {
		//			if (possible(i)) {
		//				ans = i;
		//			}
		//		}
		System.out.println(ans);
	}

	static boolean possible(long m) {
		long[] count = new long[N];
		long all = 0;
		St[] rem = new St[N];
		boolean ok = true;
		for (int i = 0; i < N; ++i) {
			count[i] = a[i] * m / sum;
			all += count[i];
			rem[i] = new St(a[i] * m - count[i] * sum, i);
			if (count[i] < b[i]) ok = false;
		}
		if (ok) return true;
		Arrays.sort(rem);
		for (int i = 0; i < Math.min(m - all, N); ++i) {
			++count[rem[i].i];
		}
		//		System.out.println(m + " " + Arrays.toString(count) + " " + all);
		for (int i = 0; i < N; ++i) {
			if (count[i] < b[i]) return false;
		}
		return true;
	}

	static class St implements Comparable<St> {
		long c;
		int i;

		St(long c, int i) {
			this.c = c;
			this.i = i;
		}

		public int compareTo(St o) {
			if (this.c == o.c) return this.i - o.i;
			if (this.c > o.c) return -1;
			return 1;
		}
	}

}

Submission Info

Judge Result