TopCoder SRM 355 Div1 Easy MixingLiquids

問題

一種類の物質を溶かした溶液がn種類ある。
それぞれの溶液の濃度はpercent[i]%で、質量はamount[i]グラムである。

溶液を自由に混ぜて、濃度need%の溶液を出来るだけ多く作りたい。
need%の溶液な何グラム出来るか、求めよ。

制約条件

n≦50
0≦percent[i],need≦100
amount[i]≦1000

方針

目的の溶液が最大量得られているとき、
目的の溶液より濃い溶液と、薄い溶液が同時に余っていることはない。
（両方余っていたら、もっと多くの目的の溶液が作れるため）

したがって、薄い溶液を全部使ってから、
濃い溶液を薄い順に入れていくやり方と、
濃い溶液を全部使ってから、薄い溶液を濃い順に入れていくやり方を両方試せば十分。

ソースコード

double solve(vector<pi> a,vector<pi> b,double x,double y,int need){
	rep(i,a.size()){
		x+=a[i].second;
		y+=a[i].second*a[i].first/100.0;
	}
	if(x==0||abs(y/x*100-need)<EPS)return x;
	
	bool sml=y/x*100<need;
	rep(i,b.size()){
		double nx=x+b[i].second, ny=y+b[i].first*b[i].second/100.0;
		
		if(sml&&ny/nx*100+EPS<need||!sml&&ny/nx*100>need+EPS)x=nx, y=ny;
		else{
			double t=(y*100.0-x*need)/(need-b[i].first);
			x+=t;
			return x;
		}
	}
	return INF;
}

class MixingLiquids {
	public:
	double howMuch(vector <int> percent, vector <int> amount, int need) 
	{
		double x=0,y=0;
		vector<pi> a,b;
		int n=percent.size();
		rep(i,n){
			if(percent[i]==need){
				x+=amount[i];
				y+=amount[i]*need/100.0;
			}
			else if(percent[i]<need)a.pb(mp(percent[i],amount[i]));
			else b.pb(mp(percent[i],amount[i]));
		}
		sort(all(a),greater<pi>());
		sort(all(b));
		
		double ans=solve(a,b,x,y,need);
		if(ans==INF)ans=solve(b,a,x,y,need);
		return ans==INF?0.0:ans;
	}
};