Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-01SRM355 (Practice)

SRM 355 MixingLiquids

|  SRM 355 MixingLiquids - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 355 MixingLiquids - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7886

  • 一度すべての溶液を混ぜる。
    • 濃度がぴったりだったら、合計をそのまま返す。
    • 濃度が薄すぎたら、一番薄いものから減らしていく。
    • 濃度が濃すぎたら、一番濃いものから減らしていく。
import java.util.Arrays;
import java.util.Comparator;

public class MixingLiquids {
	class Cup {
		int pcnt;
		int amnt;
		Cup(int p, int a) {
			pcnt = p;
			amnt = a;
		}
	}
	
	public double howMuch(int[] percent, int[] amount, int need) {
		int len = percent.length;
		Cup[] cup = new Cup[len];
		int ttl = 0;
		int cnt = 0;
		for (int i = 0 ; i < len ; i++) {
			ttl += amount[i];
			cnt += amount[i] * percent[i];
			cup[i] = new Cup(percent[i], amount[i]);
		}
		Arrays.sort(cup, new Comparator<Cup>(){
			public int compare(Cup a, Cup b) {
				return a.pcnt - b.pcnt;
			}
		});
		
		int from = 0;
		int to = len - 1;
		while (from <= to) {
			int newttl = ttl, newcnt = cnt;
			if (cnt == ttl * need) {
				return ttl;
			} else if (cnt < ttl * need) {
				newttl -= cup[from].amnt;
				newcnt -= cup[from].amnt * cup[from].pcnt;
				if (newttl * need < newcnt) {
					return ttl - (double)(cnt - ttl * need) / (cup[from].pcnt - need);
				} else {
					from++;
					ttl = newttl;
					cnt = newcnt;
				}
			} else {
				newttl -= cup[to].amnt;
				newcnt -= cup[to].amnt * cup[to].pcnt;
				if (newttl * need > newcnt) {
					return ttl - (double)(cnt - ttl * need) / (cup[to].pcnt - need);
				} else {
					to--;
					ttl = newttl;
					cnt = newcnt;
				}				
			}
		}
		return 0.0d;
	}
}