http://poj.org/problem?id=3045

50000匹の牛がピラミッド作って喜ぶ問題。どんな牛だよ。

特殊な比較関数用意でソートして貪欲に解いた。 なんか二分探索って話を師匠も工房の先生もしていたのだが・・・

二匹の牛について最大のリスクmaxRiskが最小になるような並べ方を考える。

牛C1のStrengthをS1, WeightをW1 牛C2のStrengthをS1, WeightをW2として

1. C1をC2の上に乗っけるとき maxRisk = max(-S1, -S2 + W1)

2. C2をC1の上に乗っけるとき maxRisk = max(-S2, -S1 + W2)

よって

max(-S1, -S2 + W1) > max(-S2, -S1 + W2)ならC2を下に

max(-S1, -S2 + W1) < max(-S2, -S1 + W2)ならC1を下にすればいい。同じならどっちでもいい。

ところでこれは-S2+W1と-S1+W2を比較するだけでいい。

なぜならS1, S2, W1, W2が正整数であるため

max(-S1, -S2 + W1) = -S1

max(-S2, -S1 + W2) = -S2

が同時に成立せず、

-S1 >= -S1 + W2

-S2 >= -S2 + W1

は常に成立するから。

任意の二匹についてこの並べ方を適用できるのでこれを比較関数にしてソートする。