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; }