Cow Acrobats（贪心）

原题链接

贪心题做了还没几道，而且之前做的几道也是线段覆盖问题。

看到这道题还以为是按照体重或者强壮值来排序，但是发现自己太年轻了，刚开始做的时候就觉着不会简单，而且我还只考虑了最下面的一头牛，连题意都没看懂。正解应该是按照体重和强壮值的和进行排序，证明如下：

设a在上b在下，两头牛的体重和强壮值分别为Wa, Sa, Wb, Sb。

既然没能力证真，那就先假设最优解然后证伪。

设a上面所有牛的体重和是sum，因为任意两头相邻的牛交换只会对它俩造成影响，所以不需要考虑其他牛是否会被影响。

交换前：牛a：sum - Sa

牛b：sum + Wa - Sb

交换后：牛a'：sum + Wb - Sa

　　牛b'：sum - Sb

由于交换前已经是最优解，那么交换后的最大值必定大于交换前的最大值，也就是max(a, b) < max(a', b')，接着会发现牛b' < 牛b，假设牛b'最大，也就是牛b' < max(牛a, 牛b)，即，交换后b不是最大的，所以交换后的a是最大的，且a' > max(a, b)。

也就是：sum + Sb - Sa > sum - Sa

sum + Wb - Sa > sum + Wa - Sb

化简后：Wb + Sb > Wa + Sa

这对任意两头相邻的牛都是成立的。

所以应该按照W和S的和来进行从大到小的排序，即大的在下面，小的在上面。

代码如下：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <string>
 4 using namespace std;
 5 
 6 typedef long long LL;
 7 const int N = 50010;
 8 int w[N], s[N];
 9 struct Node{
10     int w, s;
11     LL w_s;
12 }node[N];
13 
14 //按照体重从大往小排序
15 bool cmp(Node a, Node b){
16     return a.w_s >= b.w_s;
17 }
18 LL sum = 0;
19 int main(){
20     int n;
21     cin >> n;
22     for(int i = 0; i < n; i ++){
23         cin >> node[i].w >> node[i].s;
24         node[i].w_s = node[i].w + node[i].s;
25     }
26     sort(node, node + n, cmp);
27     for(int i = 0; i < n; i ++)
28         sum += node[i].w;
29     LL maxn = -0x3f3f3f3f;
30     for(int i = 0; i < n; i ++){
31         sum -= node[i].w;
32         maxn = max(maxn, sum - node[i].s);
33     }
34     cout << maxn << endl;
35 
36     return 0;
37 }