日常训练 20170708 假如爱有天意love

题面：
  有 $N\ (1\le N\le 10^5)$ 个大小为 $2$ 的栈。 Alice 和 Bob 两个人进行轮流操作,Alice 先手。 每个人每次可以取出一个栈顶的元素,获得对应的收益,具体的:第 $i$ 个栈的栈顶的元素给 Alice 的收益是 $A_i$,Bob 的收益是 $B_i$,栈底的元素给 Alice 的收益是 $C_i$,给 Bob 的收益是 $D_i$。现在 Alice 和 Bob 都想最大化自己的收益减去对方的收益。问 Alice 的收益减 Bob 的收益最后会是多少。
题解：
   拿一件物品的收益是自己拿了物品的收益加上对方没拿到的收益，那么一件物品的实际价值就是两个人估价的和了，如果上层物品价值比下面的高两个人肯定都要抢，就把上下物品都丢到数组sort一下，如果上面物品价值比下面小，谁拿上面谁倒霉，而且倒霉的肯定是先手，因为先手只要一拿上面的后手拿对应下面的肯定对后手最优，那么这些堆一定是先手取上面，后手取下面。

#include<bits/stdc++.h>
const int N = 2e4 + 10;
template <typename T> void read(T &x) {
    x = 0; T f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f *= -1;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}
struct rec{int a, b;} a[N * 2];
bool cmp(const rec &a, const rec &b) {return a.a + a.b > b.a + b.b;};
int n, a1, b1, a2, b2, cnt;
long long ans;
int main() {
    freopen("love.in", "r", stdin);
    freopen("love.out", "w", stdout);
    read(n);
    for (int i = 1; i <= n; i++) {
        read(a1), read(b1), read(a2), read(b2);
        if (a1 + b1 > a2 + b2)
            a[++cnt] = (rec) {a1, b1},
            a[++cnt] = (rec) {a2, b2};
        else
            ans += a1 - b2;
    }
    std::sort(a + 1, a + cnt + 1, cmp);
    for (int i = 1; i <= cnt; i += 2)
        ans += a[i].a - a[i + 1].b;
    printf("%lld\n", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30