hogloidのブログ

へなちょこ

PKU 3262 Protecting the Flowers

TopCoderでこれ+ナップザックな問題と昔当たったので簡単
ある牛A、Bがいて、それ以外の残りの牛の破壊量/minuteをDとおくと、
破壊量はそれぞれ
Aー>Bの順に処理すると
Aの時間*(D+Bの破壊量)+Bの時間*D
Bー>Aの順に処理すると
Bの時間*(D+Aの破壊量)+Aの時間*D
差を取ると、
Aの時間*Bの破壊量ーAの破壊量*Bの時間
差が負の時Aから処理した方がよい
これを使ってソート。あとはどんよく

struct comp{
	bool operator ()(const pi &p,const pi &p2)const{
		return (double)p.fr/p.sc<(double)p2.fr/p2.sc;
	}
};
int main(){
	int n;
	scanf("%d",&n);
	vp cow(n);
	lint des=0;
	REP(i,n){
		 scanf("%d%d",&cow[i].fr,&cow[i].sc);
		 cow[i].fr*=2;
		 des+=cow[i].sc;
	}
	sort(ALL(cow),comp());
	lint res=0;
	REP(i,n){
		des-=cow[i].sc;
		res+=des*cow[i].fr;
	}
	printf("%lld\n",res);
	return 0;
}