OUPC2012 問題E Fractional Knapsack (AOJ2354)

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2354）

制約条件

n≦10^5
w≦10^5
-10^4≦wi≦10^4
-10^4≦vi≦10^4

方針

v≧0,w≦0の品物は無条件に全て使う。
v≦0,w≧0の品物は無条件に全て捨てる。

残り、v≦0,w≦0の品物は、使ったことにして、(-v,-w)の、符号が逆の品物があることにする。
すると全ての品物がv≧0,w≧0の場合に帰着されるので、
v/wが大きい順に貪欲に使っていけばよい。

ソースコード

bool cmp(const pi &a,const pi &b){
	return a.second*b.first>a.first*b.second;
}
int n; double W;
vector<pi> p;

int main(){
	cin>>n>>W;
	double ans=0;
	rep(i,n){
		int w,v; cin>>w>>v;
		if(w<=0&&v>=0)ans+=v, W-=w;
		else if(v<=0&&w>=0)continue;
		else if(v>0&&w>0)p.pb(mp(w,v));
		else{
			p.pb(mp(-w,-v));
			ans+=v, W-=w;
		}
	}
	sort(all(p),cmp);
	for(int i=0;i<p.size();i++){
		double use=min(1.0,W/p[i].first);
		W-=use*p[i].first;
		ans+=p[i].second*use;
		if(W<EPS)break;
	}
	printf("%.12f\n",ans);
	return 0;
}