Login
Immutable PageDiscussionInfoAttachments
iz/競技プログラミング/PKU 3045 Cow Acrobats

MMA

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が正整数であるため

が同時に成立せず、

は常に成立するから。

次に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)

で計算できる。

   1 import java.io.*;
   2 import java.util.*;
   3 
   4 public class Main {
   5     BufferedReader br;
   6     Main() {
   7         br = new BufferedReader(new InputStreamReader(System.in));
   8     }
   9     public static void main(String[] args) {
  10         new Main().run();
  11     }
  12     class Cow {
  13         int W, S;
  14         Cow(int W, int S) {
  15             this.W = W;
  16             this.S = S;
  17         }
  18         public String toString() {
  19             return "W: " + W + " S: " + S;
  20         }
  21     }
  22     int N;
  23     Cow [] C;
  24     void init() {
  25         try {
  26             N = Integer.parseInt(br.readLine());
  27             C = new Cow[N];
  28             for (int i = 0; i < N; i++) {
  29                 String [] WS = br.readLine().split(" ");
  30                 C[i] = new Cow(Integer.parseInt(WS[0]), Integer.parseInt(WS[1]));
  31             }
  32             Arrays.sort(C, new Comparator<Cow>() {
  33                 @Override public int compare(Cow a, Cow b) {
  34                     return (-a.S + b.W) - (-b.S + a.W);
  35                 }
  36             });
  37         } catch (IOException e) {}
  38     }
  39     void run() {
  40         init();
  41         System.out.println(solve());
  42     }
  43     int solve() {
  44         int maxRisk = -C[0].S;
  45         for (int i = 1; i < N; i++) {
  46             maxRisk = Math.max(-C[i].S, maxRisk + C[i].W);
  47         }
  48         return maxRisk;
  49     }
  50 }

iz/競技プログラミング/PKU 3045 Cow Acrobats (last edited 2012-12-17 17:25:09 by iz)