T3
题目
有一天杜教与睿爸在争论谁才是(OI)界一哥，他们激烈辩论了半天也没有个结果。
于是毛总想了一个注意，他制作了一个游戏来帮助他们决定胜负。
游戏规则是这样的：
游戏中一共有(n)个大小为(2)的栈。两人轮流操作，睿爸先手。
每个人每次可以取出一个栈顶的元素，获得对应的收益。具体来说：第(i)个栈的栈顶的元素给睿爸的收益是(a_i) , 给杜教的收益是(b_i) ，栈底的元素给睿爸的收益是(c_i) ，给杜教的收益是(d_i) 。
同时，双方由于在这件事上面拱起了大火，所以双方博弈的目的都是要求自己的收益减去对面的收益最大。
由于双方都是(OI)界扛把子，智慧过人，所以他们都会采取对自己最优的决策。
睿爸最终想知道玩完游戏后他的收益减去杜教的收益是多少。
Solution
看起来像博弈的贪心。
我们设第(i)个元素给先手收益为(x_i)（取得的(a_i)或(c_i)）,给后手收益为(y_i)（(b_i)或(d_i)）
设先手最后取得元素集合为(A)，全集为(U)
我们对答案进行观察
你会发现这个结论是如此显然。
显然全集中(y_i)的总和是一个定值，那么我们的目的就是让((x_i + y_i))最大。
((x_i + y_i))是啥？是(a_i + b_i)或(c_i + d_i)
两者目的相同，接下来考虑一些必然策略。
-
对于(a_i + b_i <= c_i + d_i)，总是先手取栈顶，后手取栈底。当先手取栈顶之后，后手一定可以取栈底，而后手不会主动取栈顶。
说明（非证明）：若后手在先手取完栈顶之后不取栈底而去取另一个更大的栈顶，那么根据希望((x_i + y_i))最大，一开始先手就一定会取那个更大的栈顶。
然后可以先排除所有(a_i + b_i <= c_i + d_i)的栈，因为所属已经确定。
- 对于(a_i + b_i > c_i + d_i)，可以吧所有元素取出排序，再按照先手后手依次取。因为满足上式，所以不会存在先手想取的更大元素处于栈底的冲突。
(mathrm{Code:})
#include <algorithm>
#include <iostream>
const int N = 20010;
int n;
template <class T>
inline void read(T &s) {
int w = 1;
char c = getchar();
while ((c < '0' || c > '9') && c != '-') c = getchar();
if (c == '-') w = -1, c = getchar();
while (c <= '9' && c >= '0')
s = (s << 3) + (s << 1) + c - '0', c = getchar();
s *= w;
}
template <class T>
inline void write(T x) {
if (x < 0) x = ~x + 1, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
return void();
}
int bb[N], cnt = 0, A = 0, B = 0;
int ans1 = 0, ans2 = 0;
int a, b, c, d;
inline bool cmp(int x, int y) { return x > y; }
main() {
freopen("dortmund.in", "r", stdin);
freopen("dortmund.out", "w", stdout);
read(n);
for (int i = 1; i <= n; ++i) {
a = b = c = d = 0;
read(a), read(b), read(c), read(d);
A += a + c;
B += b + d;
if (a + b > c + d)
bb[++cnt] = a + b, bb[++cnt] = c + d;
else
ans1 += a + b, ans2 += c + d;
}
std ::sort(bb + 1, bb + cnt + 1, cmp);
for (int i = 1; i <= cnt; ++i) i & 1 ? ans1 += bb[i] : ans2 += bb[i];
write(ans1 - B);
return 0;
}