Submission #59001

---

Source Code Expand

import java.util.Arrays;
import java.math.BigDecimal;
import java.util.Scanner;

public class Main {

	static long[] a;
	static long[] b;
	static long s = 0;
	static int n;
	//static void test(){
	//	System.out.println(3.999 - (long)3.999);
	//}

	public static void main(String[] args) {
		doIt();
		//test();
	}
	static void doIt(){
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		a = new long[n];
		b = new long[n];
		for(int i = 0; i < n; i++){
			a[i] = sc.nextInt();
			b[i] = sc.nextLong();
		}
		for(long aa : a) s += aa;
		System.out.println(binSearch(0, 1000000000000000000L));
		//System.out.println(binSearch(0, 100));
	}
	static long binSearch(long min, long max){
		long ret = 0;
		long t = (min + max) / 2;
		boolean res = alloc(t);
		if(res)
			if(max == t) 
				if(alloc(min)) ret = min;
				else ret = t;
			else ret = binSearch(min, t);
		else 
			if(min == t) ret = max;
			else ret = binSearch(t, max);
		return ret;
	}
	static boolean alloc(long m){
		boolean ret = true;
		long[] cand = new long[n];
		CAT[] ary = new CAT[n];
		long tm = m;
		for(int i = 0; i < n; i++){
			//double t = 0;
			BigDecimal ta = BigDecimal.valueOf( a[i] );
			BigDecimal tmm = BigDecimal.valueOf( m );
			BigDecimal ts = BigDecimal.valueOf( s );
			//BigDecimal t = (double)a[i] * (double)m / (double)s;
			BigDecimal t = (ta.multiply(tmm));
			//t = t.divide(ts, 40, BigDecimal.ROUND_HALF_EVEN);
			//t = (double)a[i] * (double)m / (double)s;
			//cand[i] += (long)t;
			BigDecimal tt = t.divideToIntegralValue(ts);
			cand[i] += tt.longValue();
			tm -= cand[i];
			ary[i] = new CAT((t.divide(ts, 1000, BigDecimal.ROUND_HALF_EVEN)).subtract(tt), i);
		}
		if(tm > 0){
			Arrays.sort(ary);
			int i = 0;
			while(tm > 0){
				cand[ary[i].id]++;
				tm--;
				i++;
				if(i >= n) i = 0;
			}
		}
		for(int i = 0; i < n; i++){
			if(b[i] > cand[i]){ ret = false; break;}
		}
		return ret;
	}
}

class CAT implements Comparable<CAT> {
	public BigDecimal dec;
	public int id;
	//public double db;
	CAT(BigDecimal r, int n) {
		dec = r;
		id = n;
		//db = r.doubleValue();
	}
	public int compareTo(CAT arg0) {
		return (dec.compareTo(((CAT)arg0).dec))*-1;
		//(dec - ((CAT)arg0).dec < 0)? 1 : -1;
	}
}

Submission Info

Judge Result