Poj 3045: Cow Acrobats

poj3045.md

Poj 3045: Cow Acrobats

題目

分析

最大值最小化 => …不是二分搜，卻是 Greedy 啊 （這題也可用二分搜來解，但較慢，可參 這 ，雖然我是看不太懂啦…）

依照 s + w 來排序，值越大的牛排在越前面，這個順序保證擁有最小的最大風險

但為什麼是 s + w 呢？而不是 s / w, w / s, s - w, etc

證明

反證法

假設

... Cow1 Cow2 ... (s1 + w1 < s2 + w2)    ----- (1)

為最佳解，則

Let W = 那兩隻牛後面所有牛的重量總和

risk1 = w2 + W - s1
risk2 = W - s2

我們可以交換 Cow1, Cow2

... Cow2 Cow1 ... (s1 + w1 < s2 + w2)    ----- (2)

可得

risk1' = W - s1
risk2' = w1 + W - s2

---

比較 (2) 與 (1) 的最大風險值，即

max(risk1', risk2')
與
max(risk1, risk2)

展開式子

max(W - s1, w1 + W - s2)
與
max(w2 + W - s1, W - s2)

同 - W + s1 + s2，相對的大小不變，得

max(s2, w1 + s1)    ----- (3)
與
max(w2 + s2, s1)    ----- (4)

若 (3) = s2， (4) 中的 w2 + s2 必 > s2，所以 (3) < (4)；

若 (3) = w2 + s2，由 (2) 可知 s1 + w1 < s2 + w2，所以 (3) < (4)。

所以我們得到結論

(3) < (4)

也就是說

max(risk1', risk2') < max(risk1, risk2)

這代表 (2) 是一個比 (1) 好的順序，因 (2) 的最大風險值比 (1) 的最大風險值小， 所以假設不成立，我們也由此知

最佳解中任相鄰二隻牛必有性質 s1 + w1 >= s2 + w2

一般證法

設最佳解

... Cow1 Cow2 ...     ----- (1)

其中

Let W = 那兩隻牛後面所有牛的重量總和

risk1 = w2 + W - s1
risk2 = W - s2

交換 Cow1, Cow2

... Cow2 Cow1 ...    ----- (2)

則

risk1' = W - s1
risk2' = w1 + W - s2

(1) 是最佳解

 -> (1) 比 (2) 有較小的最大風險
<-> max(risk1, risk2) <= max(risk1', risk2')
<-> max(w2 + W - s1, W - s2) <= max(W - s1, w1 + W - s2)

同 - W + s1 + s2，相對的大小不變，得

(續)
<-> max(w2 + s2, s1)    ----- (3)
    <= max(s2, w1 + s1)    ----- (4)

若 (3) = s1，因 (4) 中的 w1 + s1 必 > s1，所以不等式必成立

若 (3) = w2 + s2，因 w2 + sw 必 > (4) 中的 s2，所以不等式成立於

w2 + s2 <= w1 + s1

於是我們得到結論

(續)
<-> w2 + s2 <= w1 + s1
<-> w1 + s1 >= s2 + s2

(1) 是最佳解

iff 在序列中，任相鄰的兩隻牛都使 (3) <= (4) 成立，即 w1 + s1 >= s2 + s2

得證。

AC Code

#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef long long ll;
const int INF = 0x3f3f3f3f;

struct Cow {
    int w, s;

    bool operator > (const Cow& c) const {
        return w + s > c.w + c.s;
    }
};

int N;
Cow cows[50000];

ll solve() {
    sort(cows, cows + N, greater<Cow>());

    ll W = 0;
    for (int i = 0; i < N; i++)
        W += cows[i].w;

    ll max_risk = -INF;
    for (int i = 0; i < N; i++) {
        W -= cows[i].w;
        ll risk = W - cows[i].s;
        if (risk > max_risk)
            max_risk = risk;
    }

    return max_risk;
}

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        scanf("%d %d", &cows[i].w, &cows[i].s);

    printf("%lld\n", solve());

    return 0;
}

感謝分享！
:)