SRM 355 300pt : MixingLiquids

keyword

二分探索　誤差　中間値の定理　C++

問題概要

濃度p[i]%の液体がa[i]リットルある。濃度need%の液体を最大でどれだけつくることができるか求める問題。

解法

答えに関して二分探索する。xリットルの液体を作るとき、濃度の低い順にxリットル取ってきたものの濃度をL, 濃度の高い順にxリットル取ってきたものの濃度をHとすると、L < need < Hならば、中間値の定理より濃度need%の液体を作ることができる。
ただし、濃度LとHを求めるときに誤差がはいるので、そこは注意してやる（二分探索の中でEPSをどうしても使わなければならないときは、許容誤差よりもかなり小さめに取っておくとよい）。
ちなみに上位陣の回答は何か整数のまま上手いことやっている。

感想

マシンイプシロンがどの位か知っておけばEPSを自信持って定めることができるんだけど、そういう苦労は避ける方向でやりたい。

#include <vector>
#include <algorithm>
using namespace std;

struct MixingLiquids {

	double howMuch(vector <int> percent, vector <int> amount, int need) {
		vector< pair<double, double> > as;
		double nd = need/100.0;
		int N = percent.size();
		double total_amount = 0.0;
		for(int i=0; i<N; i++){
			as.push_back( make_pair(percent[i]/100.0, amount[i]) );
			total_amount += amount[i];
		}
		sort(as.begin(), as.end());
		double low = 1e-10, high = total_amount;
		for(int loop = 0; loop < 100; loop++){
			double mid = (low + high)*0.5;
			{
				double cur_amount =0.0, cur_dense = 0.0;
				for(int i=0; i<N; i++){
					if(cur_amount + as[i].second < mid){
						cur_dense = (cur_dense*cur_amount +  as[i].first*as[i].second)/(cur_amount + as[i].second);
						cur_amount += as[i].second;
					}
					else{
						cur_dense = (cur_dense*cur_amount +  as[i].first*(mid - cur_amount))/mid;
						break;
					}
				}
				if(cur_dense > nd + 1e-12){
					high = mid;
					continue;
				}
			}
			{
				double cur_amount =0.0, cur_dense = 0.0;
				for(int i=N-1; i>=0; i--){
					if(cur_amount + as[i].second < mid){
						cur_dense = (cur_dense*cur_amount +  as[i].first*as[i].second)/(cur_amount + as[i].second);
						cur_amount += as[i].second;
					}
					else{
						cur_dense = (cur_dense*cur_amount +  as[i].first*(mid - cur_amount))/mid;
						break;
					}
				}
				if(cur_dense < nd - 1e-12){
					high = mid;
					continue;
				}
			}
			low = mid;
		}
		return low;
	}

};