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 

は常に成立するから。

次に3匹の並べ方について考える。

3匹C1(S1, W1), C2(S2, W2), C3(S3, W3)がいて、C1とC2ではC1を上にC2を下にするのが最適で、C2とC3ではC2を上にC3を下にするのが最適であることが分かっていると仮定する。
このときC1とC3ではC1を上にC3を下にするのが最適なら、任意の二匹についてこの並べ方を適用できる。

仮定から、
-S2 + W1 >= -S1 + W2,
-S3 + W2 >= -S2 + W3
2式を足して、
-S3 + W1 >= -S1 + W3
よってC1とC3ではC1を上にC3を下にするのが最適

これを比較関数にしてソートする。

maxRiskの最小値については牛を下から順に積んでいくと考える。

初期値をmaxRisk = -(一番下の牛のStrength)として、

ある牛C（Strength: S, Weight: W）をてっぺんに乗っけるとき
下の牛すべてについてriskがWだけ増えるので

maxRisk = max(-S, maxRisk + W)

で計算できる。


{{{#!highlight java
import java.io.*;
import java.util.*;

public class Main {
    BufferedReader br;
    Main() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }
    public static void main(String[] args) {
        new Main().run();
    }
    class Cow {
        int W, S;
        Cow(int W, int S) {
            this.W = W;
            this.S = S;
        }
        public String toString() {
            return "W: " + W + " S: " + S;
        }
    }
    int N;
    Cow [] C;
    void init() {
        try {
            N = Integer.parseInt(br.readLine());
            C = new Cow[N];
            for (int i = 0; i < N; i++) {
                String [] WS = br.readLine().split(" ");
                C[i] = new Cow(Integer.parseInt(WS[0]), Integer.parseInt(WS[1]));
            }
            Arrays.sort(C, new Comparator<Cow>() {
                @Override public int compare(Cow a, Cow b) {
                    return (-a.S + b.W) - (-b.S + a.W);
                }
            });
        } catch (IOException e) {}
    }
    void run() {
        init();
        System.out.println(solve());
    }
    int solve() {
        int maxRisk = -C[0].S;
        for (int i = 1; i < N; i++) {
            maxRisk = Math.max(-C[i].S, maxRisk + C[i].W);
        }
        return maxRisk;
    }
}
}}}