Greedy:Cow Acrobats(POJ 3045)

　　　　　　　　　　　

　　　　　　　　　　　　　　　　牛杂技团

　　题目大意：一群牛想逃跑，他们想通过搭牛梯来通过，现在定义risk（注意可是负的）为当前牛上面的牛的总重量-当前牛的strength，问应该怎么排列才能使risk最小？

　　说实话这道题我一开始给书上的二分法给弄懵了，后来看了一下题解发现根本不是这么一回事，其实就是个简单的贪心法而已。

　　这题怎么贪心呢？就是按w+s从小到大排序就好了，证明一下：

　　1.先证明如果不满足w+s的序列性，无论谁在谁的上面，都会违反题设：（设A在B的上面）

　　　　如果 A.s+A.w<B.s+B.w

　　　　则如果B.s<m+A.w

　　　　则如果B在A的上面A.s<B.s+B.w-A.w=B.w+m

　　　　得证

　　2.再证明一下如果采用排序的确能让risk的最大值最小。

　　　　如果 A.s+A.w<B.s+B.w

　　　　①A在B的上面

　　　　riskA1=m-A.s  riskB1=m+A.w-B.s

　　　　②B在A的上面

　　　　riskB2=m-B.s  riskA2=m+B.w-A.s

　　　　所以riskA2>riskA1

　　　　　　另外riskB1-riskA2=A.w+A.s-B.w-B.s<0  所以riskA2>riskB1>riskB2

　　　　则违反后risk会产生一个比三个risk更大的数，不符合题意

　　　　参考http://poj.org/showmessage?message_id=341726

 #include <iostream>

 #include <algorithm>

 #include <functional>

 using namespace std;

 typedef long long LL_INT;

 typedef struct _cows

 {

     LL_INT strength;

     LL_INT weight;

     bool operator<(const  _cows &x) const

     {

         return strength + weight > x.weight + x.strength;

     }

 }Cows;

 static Cows cows_set[];

 void Search(const int, LL_INT);

 bool judge(const LL_INT, const int,const LL_INT);

 int main(void)

 {

     int sum_cows;

     LL_INT sum_w;

     while (~scanf("%d", &sum_cows))

     {

         sum_w = ;

         for (int i = ; i < sum_cows; i++)

         {

             scanf("%lld%lld", &cows_set[i].weight, &cows_set[i].strength);

             sum_w += cows_set[i].weight;

         }

         sort(cows_set, cows_set + sum_cows);

         Search(sum_cows,sum_w);

     }

     return ;

 }

 void Search(const int sum_cows, LL_INT sum_w)

 {

     LL_INT ans = -;

     for (int i = ; i < sum_cows; i++)

     {

         sum_w -= cows_set[i].weight;

         ans = max(ans, sum_w - cows_set[i].strength);

     }

     cout << ans << endl;

 }

其实这题的思想和Protecting Flowers那题有点像，都是只看两个元素之间的两个量之间的练联系，而不只是单单的一个量