PKU3045-Cow Acrobats

題目：http://poj.org/problem?id=3045
FJ有N(50000)頭牛，每頭牛有自己的重量W_i和力量S_i
現在這些牛想要玩疊羅漢
每隻牛承受的風險值=自己頭上所有牛的重量和-力量
某個疊羅漢方法它倒塌的危險相當於風險最大那頭牛的風險值
問最優的情形下最小的危險度



程式碼：codpad掛了，待補

有種毛毛蟲問題(謀事在人)的感覺

這題的解法我是從一個問題開始：應該選誰當最底下那頭牛？
(以下設所有牛的總重=T)
重量30 27 22 18 13
力量15 20 14 22 28

嘗試去計算每頭牛當最底牛的風險
這個值剛好是(T-W_i)-S_i (別人的重量和-自己的力量)
而T正好是個常數，如果把T和(W_i+S_i)分開來的話表格會像是這樣：

重量	30	27	22	18	13
力量	15	20	14	22	28
風險	90-45	90-47	90-36	90-40	90-41

用肉眼看過去然後感性的猜猜看，選(27,20)這頭牛好了、風險值最小
不過我們想知道選走(27,20)以後，剩下的牛如果也這麼選是否是最優解呢？
答案就是最優解

重量	30	22	18	13
力量	15	14	22	28
風險	63-45	63-36	63-40	63-41

由於把(27,20)選走以後
其實只是讓常數T直接往下扣27而已
所有牛的風險變化量都一樣、大小關係當然也和本來一樣
可以快樂的繼續選走(30,15)當倒數第二牛仍然是最優的

得出貪心算法「把W_i+S_i最大的牛盡量壓下面」，解開本題