|
サイズ: 2928
コメント:
|
サイズ: 2940
コメント:
|
| 削除された箇所はこのように表示されます。 | 追加された箇所はこのように表示されます。 |
| 行 96: | 行 96: |
| int risk = -C[0].S; | int maxRisk = -C[0].S; |
| 行 98: | 行 98: |
| risk = Math.max(-C[i].S, risk + C[i].W); | maxRisk = Math.max(-C[i].S, maxRisk + C[i].W); |
| 行 100: | 行 100: |
| return risk; | return maxRisk; |
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
は常に成立するから。
任意の二匹についてこの並べ方を適用できるのでこれを比較関数にしてソートする。
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 }
