|
サイズ: 1184
コメント:
|
サイズ: 1211
コメント:
|
| 削除された箇所はこのように表示されます。 | 追加された箇所はこのように表示されます。 |
| 行 5: | 行 5: |
| 特殊な比較関数用意でソートして貪欲に解いた。 なんか二分探索って話を師匠も工房の先生もしていたのだが・・・ |
特殊な比較関数用意でソートして貪欲に解いた。 なんか二分探索って話を師匠も工房の先生もしていたのだが・・・ |
| 行 9: | 行 9: |
| 牛C1のStrengthをS1, WeightをW1 牛C2のStrengthをS1, WeightをW2として |
|
| 行 12: | 行 10: |
| 1. C1をC2の上に乗っけるとき maxRisk = max(-S1, -S2 + W1) |
牛C1のStrengthをS1, WeightをW1 牛C2のStrengthをS1, WeightをW2として |
| 行 15: | 行 12: |
| 2. C2をC1の上に乗っけるとき maxRisk = max(-S2, -S1 + W2) |
1. C1をC2の上に乗っけるとき maxRisk = max(-S1, -S2 + W1) 2. C2をC1の上に乗っけるとき maxRisk = max(-S2, -S1 + W2) |
| 行 19: | 行 17: |
| 行 20: | 行 19: |
| max(-S1, -S2 + W1) < max(-S2, -S1 + W2)ならC1を下に すればいい。同じならどっちでもいい。 |
max(-S1, -S2 + W1) < max(-S2, -S1 + W2)ならC1を下にすればいい。同じならどっちでもいい。 |
| 行 24: | 行 23: |
| 行 25: | 行 25: |
| max(-S1, -S2 + W1) = -S1 max(-S2, -S1 + W2) = -S2 |
* max(-S1, -S2 + W1) = -S1 * max(-S2, -S1 + W2) = -S2 |
| 行 28: | 行 31: |
| -S1 >= -S1 + W2 -S2 >= -S2 + W1 |
* -S1 >= -S1 + W2 * -S2 >= -S2 + W1 |
| 行 33: | 行 39: |
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
は常に成立するから。
任意の二匹についてこの並べ方を適用できるのでこれを比較関数にしてソートする。
