POJ 3045 -- Cow Acrobats
一群奶牛，每只有重量W与力量S。现在把它们摞成一个stack，定义每只牛的「风险」是它上面所有牛的重量减去它自己的力量。找出一种排列方式让所有牛中最大的风险最小。输出这个最小的最大风险
事实上，牛的叠放顺序可以确定，并且相当方便。凭感觉，力量越大、体重越大的牛应该放在越下面，否则浪费力气。所以按下面的代码排过序后就是叠放顺序，然后顺序找出最大risk即可。
http://blog.csdn.net/kimi_r_17/article/details/26613369
http://tideline.logdown.com/posts/199531-poj-3045
Read full article from 3045 -- Cow Acrobats
Description
Farmer John's N (1 <= N <= 50,000) cows (numbered 1..N) are planning to run away and join the circus. Their hoofed feet prevent them from tightrope walking and swinging from the trapeze (and their last attempt at firing a cow out of a cannon met with a dismal failure). Thus, they have decided to practice performing acrobatic stunts.
The cows aren't terribly creative and have only come up with one acrobatic stunt: standing on top of each other to form a vertical stack of some height. The cows are trying to figure out the order in which they should arrange themselves ithin this stack.
Each of the N cows has an associated weight (1 <= W_i <= 10,000) and strength (1 <= S_i <= 1,000,000,000). The risk of a cow collapsing is equal to the combined weight of all cows on top of her (not including her own weight, of course) minus her strength (so that a stronger cow has a lower risk). Your task is to determine an ordering of the cows that minimizes the greatest risk of collapse for any of the cows.
The cows aren't terribly creative and have only come up with one acrobatic stunt: standing on top of each other to form a vertical stack of some height. The cows are trying to figure out the order in which they should arrange themselves ithin this stack.
Each of the N cows has an associated weight (1 <= W_i <= 10,000) and strength (1 <= S_i <= 1,000,000,000). The risk of a cow collapsing is equal to the combined weight of all cows on top of her (not including her own weight, of course) minus her strength (so that a stronger cow has a lower risk). Your task is to determine an ordering of the cows that minimizes the greatest risk of collapse for any of the cows.
Input
* Line 1: A single line with the integer N.
* Lines 2..N+1: Line i+1 describes cow i with two space-separated integers, W_i and S_i.
* Lines 2..N+1: Line i+1 describes cow i with two space-separated integers, W_i and S_i.
Output
* Line 1: A single integer, giving the largest risk of all the cows in any optimal ordering that minimizes the risk.
Sample Input
3 10 3 2 5 3 3
Sample Output
2http://www.hankcs.com/program/cpp/poj-3045-cow-acrobats.html
一群奶牛，每只有重量W与力量S。现在把它们摞成一个stack，定义每只牛的「风险」是它上面所有牛的重量减去它自己的力量。找出一种排列方式让所有牛中最大的风险最小。输出这个最小的最大风险
事实上，牛的叠放顺序可以确定，并且相当方便。凭感觉，力量越大、体重越大的牛应该放在越下面，否则浪费力气。所以按下面的代码排过序后就是叠放顺序，然后顺序找出最大risk即可。
http://blog.csdn.net/kimi_r_17/article/details/26613369
思路：一开始想当然先w后s排序然后wa了。。。若相邻两头牛属性分别为w1,s1,w2,s2,第一头牛在第二头上面，sum为第一头牛上面的牛的体重之和，那么
第一头牛风险：a=sum-s1;第二头牛风险:b=sum+w1-s2;交换两头牛位置之后a'=sum+w2-s1,b'=sum-s2，如
果要最优放置则max(a,b)<max(a',b'),因为b>b'所以要满足b<a'。即w1+s1<w2+s2。所以按照w+s排序。
第一头牛风险：a=sum-s1;第二头牛风险:b=sum+w1-s2;交换两头牛位置之后a'=sum+w2-s1,b'=sum-s2，如
果要最优放置则max(a,b)<max(a',b'),因为b>b'所以要满足b<a'。即w1+s1<w2+s2。所以按照w+s排序。
思路：假设某一种叠放次序，对于第i，i+1两个砖块来说，他们的次序谁在上谁在下对i以前和i+1以后的都没有
影响。设W为第i块上面的值：（t1、t2分别为上面、下面的ti值）
（1）第i块在上，则t1=W-si,t2=W+wi-si+1,此时最大值p=max(t1,t2)=max(W-si,W+wi-si+1);
（2）第i+1块在上，则t1=W-si+1,t2=W+wi+1-si，此时最大值q=max(t1,t2)=max(W-si+1,W+wi+1-si);
若p<q，则max(W-si,W+wi-si+1)<max(W-si+1,W+wi+1-si),同时加上si+si+1-W，即：
则max(si+1,si+wi)<max(si,si+1+wi+1)，所以只需：si+wi<si+1+wi+1。所以只需按照si+wi升序排列，扫描一遍即可。
struct Cow{ int weight, strength; bool operator < (const Cow& other) const { return other.strength + other.weight < strength + weight; }};Cow cow[MAX_N];///////////////////////////SubMain//////////////////////////////////int main(int argc, char *argv[]){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);#endif std::ios::sync_with_stdio(false); std::cin.tie(0); int N; cin >> N; int total = 0; for (int i = 0; i < N; ++i) { cin >> cow[i].weight >> cow[i].strength; total += cow[i].weight; } sort(cow, cow + N); int risk = 0x80808080; for (int i = 0; i < N; ++i) { total -= cow[i].weight; // 减去自己的重量 risk = max(risk, total - cow[i].strength); // 计算risk } cout << risk << endl; #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt");#endif return 0;}Read full article from 3045 -- Cow Acrobats
