题目链接：

题意：

　　有n头牛在“叠罗汉”。

　　第i头牛的体重为w[i]，力量为s[i]。

　　一头牛的压扁程度 = 它上面所有牛的体重之和 - s[i]

　　所有牛的总压扁程度 = 所有牛中最大的那个压扁程度

　　问你总压扁程度最小为多少。

 

题解：

　　贪心。

　　套路：

　　　　选取最小的一个单元——相邻的两头牛，进行贪心策略的局部证明。

 

　　贪心策略：

　　　　假设最左边为顶部，最右边为底部。

　　　　从左往右分别编号0...n-1。

　　　　考虑两头相邻的牛：交换i和i+1两头牛。

　　　　压扁程度（交换之前）：

　　　　　　i: a = sum - s[i]

　　　　　　i+1: b = sum + w[i] - s[i+1]

　　　　压扁程度（交换之后）：

　　　　　　i: a' = sum + w[i+1] - s[i]

　　　　　　i+1: b' = sum - s[i+1]

　　　　显然：在交换之前，b为两者最大值；交换之后，a'为两者最大值。

　　　　假设未交换时为最优状态，则交换后不可能更优。

　　　　所以有：b < a'

　　　　即：sum + w[i] - s[i+1] < sum + w[i+1] - s[i]

　　　　整理得：s[i+1] + w[i+1] > s[i] + w[i]

　　　　所以贪心策略为：w+s值越大，越放在底下。

 

AC Code:

1 // before: 2 // i: sum - s[i] 3 // i+1: sum + w[i] - s[i+1] 4 // after: 5 // i+1: sum - s[i+1] 6 // i: sum + w[i+1] - s[i] 7 // 8 // f1 < f4  +w[i+1] 9 // f2 > f3  -w[i]10 // w[i] - s[i+1] < w[i+1] - s[i]11 // w[i+1] + s[i+1] > w[i] + s[i]12 #include 
     
      13 #include 
      
       14 #include 
       
        15 #include 
        
         16 #define MAX_N 5000517 #define INF 1000000018 19 using namespace std;20 21 struct Cow22 {23     int w;24     int s;25     Cow(int _w,int _s)26     {27         w=_w;28         s=_s;29     }30     Cow(){}31     friend bool operator < (const Cow &a,const Cow &b)32     {33         return a.w+a.s
         
          >n;43     for(int i=0;i
          
           >cow[i].w>>cow[i].s;46 }47 sort(cow,cow+n);48 int sum=0;49 int ans=-INF;50 for(int i=0;i