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