相当于有 n n n 头奶牛在叠罗汉。每头牛都有两个特质，一个是重量 w w w，一个是强壮度 s s s。 每头牛都有一个崩溃风险，该风险等于在她上面的所有奶牛的总重量减去她本身的强壮度。所以每头牛都要找到合适自己的位置。 求：确定所有奶牛的位置，从而使任何奶牛中的最大风险最小。
芜湖~~先贪心试一下。 将每头牛按照 w + s w+s w+s 从小到大排序，这样就得到正确的答案啦哈哈哈哈哈哈。
设最优解为 r e a l _ a n s real\_ans real_ans，自己方案的解为 a n s ans ans。
要证： a n s = r e a l _ a n s ans=real\_ans ans=real_ans 只需证：
a n s ≤ r e a l _ a n s ans\leq real\_ans ans≤real_ans a n s ≥ r e a l _ a n s ans\ge real\_ans ans≥real_ans证明如下：
1、由题意可知，必然有 r e a l _ a n s ≤ a n s real\_ans\leq ans real_ans≤ans。
2、假设最优解不是按我们的算法来做的，则至少有一对牛是交换了位置的。已知第 k k k 头牛的特征为 ( w k , s k ) (w_k,s_k) (wk,sk)，第 k + 1 k+1 k+1 头牛的特征为 ( w k + 1 , s k + 1 ) (w_{k+1},s_{k+1}) (wk+1,sk+1)，且她们的风险分别为， r i s k , r i s k + 1 ris_k,ris_{k+1} risk,risk+1，则：
位置交换前交换后 k k k r i s k = ∑ i = 1 k − 1 w i − s k ris_k=\sum_{i=1}^{k-1}w_i-s_k risk=∑i=1k−1wi−sk r i s k = ∑ i = 1 k − 1 w i + w k + 1 − s k ris_k=\sum_{i=1}^{k-1}w_i+w_{k+1}-s_k risk=∑i=1k−1wi+wk+1−skk+1 r i s k + 1 = ∑ i = 1 k w i − s k + 1 ris_{k+1}=\sum_{i=1}^kw_i-s_{k+1} risk+1=∑i=1kwi−sk+1 r i s k + 1 = ∑ i = 1 k − 1 w i − s k + 1 ris_{k+1}=\sum_{i=1}^{k-1}w_i-s_{k+1} risk+1=∑i=1k−1wi−sk+1同时减去 ∑ i = 1 k − 1 w i \sum_{i=1}^{k-1}w_i ∑i=1k−1wi 可得：
位置交换前交换后 k k k − s k -s_k −sk w k + 1 − s k w_{k+1}-s_k wk+1−sk k + 1 k+1 k+1 w k − s k + 1 w_k-s_{k+1} wk−sk+1 − s k + 1 -s_{k+1} −sk+1由于 s , w ≥ 1 s,w\ge1 s,w≥1，所以有： w k + 1 − s k > − s k w_{k+1}-s_k>-s_k wk+1−sk>−sk, w k − s k + 1 > − s k + 1 w_{k}-s_{k+1}>-s_{k+1} wk−sk+1>−sk+1
所以，我们只要比较 w k + 1 − s k w_{k+1}-s_k wk+1−sk 与 w k − s k + 1 w_k-s_{k+1} wk−sk+1 的大小关系即可。 两边同时加上 s k + s k + 1 s_k+s_{k+1} sk+sk+1 得： w k + 1 + s k + 1 w_{k+1}+s_{k+1} wk+1+sk+1 与 w k + s k w_k+s_k wk+sk。 因为我们的贪心算法是按照 w + s w+s w+s 从小到大排序的。 所以， w k + 1 + s k + 1 ≥ w k + s k w_{k+1}+s_{k+1}\ge w_k+s_k wk+1+sk+1≥wk+sk。 所以，交换前的解要小于交换后的解，即 a n s ≤ r e a l _ a n s ans\leq real\_ans ans≤real_ans。
综上， a n s = r e a l _ a n s ans=real\_ans ans=real_ans。证毕。
