[USACO2005][POJ3045]Cow Acrobats(貪心)

題目：

題意：每個牛都有一個wi和si，試将他們排序，每頭牛的風險值等于前面所有牛的wj(j<i)之和-si，求風險值最大的牛的最小風險值

分析：這就是noip2012 T2的來源= =隻不過這裡是加，noip裡是乘

不妨設所有牛都按最優順序排好了，考慮相鄰的兩頭牛i和i+1，如果交換他們的位置，那麼對前面和後面的結果都無影響，隻是他們兩個的風險值變化了（變大了），于是我們可以得到這個時候i和i+1的關系

設w1+w2+...+wi-1=W

那麼如果i和i+1不交換：

i的風險值：W-si              ①

i+1的風險值：W+wi-si+1               ②

如果i和i+1交換：

i+1（現在在第i個位置）的風險值：W-si+1        ③

i（現在在第i+1個位置)的風險值：W+wi+1-si       ④

很容易可以看出②>③，④>①，而又假設原順序是最優的，那麼後來交換後肯定不是最優的，即②<④，即wi+si<wi+1+si+1，即最優序列一定滿足wi+si<wi+1+si+1

是以算法很簡單，按wi+si排序即可

總結：看見求最大的最小不能定式思維二分，當二分不行時可以觀察題目的特點，抓住特點很重要