SRM 355 Div2 Hard MixingLiquids

問題

n個の溶液があり、それぞれの濃度はpercent[i]%, 量はamount[i]である。
溶液を自由に混ぜてneed%の溶液をできるだけ多く作りたい。

作ることができるneed%の溶液の量の最大値を求めよ。

制約条件

n≦50

方針

needより濃い溶液、薄い溶液に分けて、
濃い溶液のうち最も薄いもの、薄い溶液のうちもっとも濃いものから、
順にneed%を維持するように混ぜていけば最大量の目的の溶液が出来ると思って、
そんなコードを無理矢理書いたら通った。

もっとスマートに考えることができる。
needより濃い溶液同士、薄い溶液同士をあらかじめ全て混ぜてしまう。
ここからneedの溶液を作ると考えると、どちらかは全て使い切る。

したがって使い切るほうの溶液の量に応じて、もう一方の溶液の量を決めてやればよいことになる。

ソースコード

スマートでないほう。

class MixingLiquids {
	public:
	double howMuch(vector <int> percent, vector <int> amount, int need) 
	{
		int n=percent.size();
		vector<pd> big,small;
		double ans=0;
		
		rep(i,n){
			if(percent[i]==need)ans+=amount[i];
			else if(percent[i]>need)big.pb(mp(percent[i]/100.0,amount[i]));
			else small.pb(mp(percent[i]/100.0,amount[i]));
		}
		sort(all(big)); sort(all(small),greater<pd>());
		
		double N=need/100.0;
		
		while(!big.empty()&&!small.empty()){
			double b=big[0].second, s=small[0].second;
			double pb=big[0].first, ps=small[0].first;
			
			double maxb=(N*s-s*ps) / (pb-N), maxs=(N*b-b*pb) / (ps-N);
			if(maxb>b){
				ans+=maxs+b;
				
				big.erase(big.begin());
				small[0].second-=maxs;
				if(small[0].second<EPS)small.erase(small.begin());
			}
			else{
				ans+=maxb+s;
				
				small.erase(small.begin());
				big[0].second-=maxb;
				if(big[0].second<EPS)big.erase(big.begin());
			}
		}
		return ans;
	}
};