贪心：临项交换 & 带悔贪心

模拟赛遇见临项交换和带悔贪心时确实想了一下他们的区别和应用范围，因为差点用错，但并没有深入思考。今天老师又提到了这个问题，来写一下。

一般这一类题目的特点：需要选择的元素有两个权值，均对所求答案的排列顺序、统计造成影响。

临项交换：排序，每次用相邻两项进行比较交换。

一般思路：如果先选 a 再选 b，这种选择的先后顺序会对 b 造成什么影响。若先选 b 再选 a，这种选择的顺序对 a 又造成什么影响。影响一般就指代价。然后比较两种代价，哪一种排序方式的代价最小就采取哪种。

我们注意到这种交换，对于这两项之外的其他项都不会造成影响，只对两项自身选择有影响。所以仅在对于其他项不会对相邻两项产生影响的情况下可以使用。

带悔贪心：选择时无论当前的选项是否最优都存下来，在后面的选择中与之进行比较，如果选择之后不再最优，则反悔，舍弃掉这个选项；否则，正式接受。如此往复。

可以发现，这类题目中，当前的选择不光对自己有影响，也会对序列中其他项的选择情况造成影响。

常用优先队列维护之前已经选择的选项。一般难度在于怎么反悔。

感觉带悔贪心还是比较抽象的。

一个临项交换例题：洛谷 P1842 奶牛玩杂技。本来想贴国王游戏，那道题确实更经典，但是发现我没写，因为需要高精度，而且题目本身也略复杂不适合做例题（？）（别问，问就是找借口）（不重要了，有空会补上。）

大概就是说每个奶牛有自己的体重 w 和力量 s，奶牛需要叠放在一起，对于下面的牛受到的压力，是其上的奶牛重量和累加，如果超出其力量则会产生危险指。找一个排列顺序使得所有奶牛最大的危险指数最小。（这个时候刚看到有最大值最小，那么也能用二分做）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll ans = -0x7fffffff, tot = 0;
struct niu{int w;ll s;} a[50010];
bool cmp(niu x, niu y) {return x.s + x.w < y.s + y.w;}
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++ ) scanf("%d%d", &a[i].w, &a[i].s);
    sort(a + 1, a + n + 1, cmp);
    for(int i = 1; i <= n; i ++ )
        {
        ans = max(ans, tot - a[i].s);
        tot += a[i].w;
    }
    printf("%lld", ans);
    return 0;
}