CF725F 做题记录
yang_cm
·
·
题解
https://www.luogu.com.cn/problem/CF725F
Problem
有 n 堆照片，每堆有两张，拿走上面一张才能拿下面的。
Alice 拿走第 i 堆的第 j\in[1,2] 张可以获得 a_{ij} 的积分，Bonnie 则可以获得 b_{ij} 的积分。两人都有权力从一堆中拿走一张或者不拿。
令 Alice 的最终积分为 x，Bonnie 的为 y，求最大的 x-y。
Solution
题目要求最大化 x-y，我们考虑 Alice 取了一张 (a,b) 的照片对这个值的贡献。
同理，如果被 Bonnie 拿到，净贡献就是 $-(a+b)$。
既然净贡献都与 $a+b$ 直接相关，$a+b$ 就是这张照片的价值。
再考虑本题的简化情况：假如每堆只有一张照片。
显然无论哪个人每次都会取 $a+b$ 最大的一张照片。把 $a+b$ 丢进大根堆贪心即可。
但是本题中每堆有两张照片，于是我们考虑比较这两张照片的价值。
假设当前堆的两个照片分别为 $(a_1,b_1),(a_2,b_2)$，前者在上，对这俩的价值大小分类讨论。
倘若 $a_1+b_1\ge a_2+b_2$，那肯定不会有人为了第二张照片放弃第一张，此时两张照片相互独立，因为第一张价值更大，必然会被先取，「先取第一张才能取第二张」的依赖关系自然成立。
若 $a_1+b_1<a_2+b_2$，此时第二张更好，我们需要观察最坏的情况：即我方拿走第一张，对方拿走第二张时，是否依然对我方有利。
对 Alice，最坏价值为 $v_A=a_1-b_2$，对 Bonnie 最坏价值为 $v_B=b_1-a_2$。
考虑将这两个价值分别与 $0$ 比较，有四种情况。
1. $v_A\le 0,v_B\le 0$，显然不会有人动。
2. $v_A>0,v_B\le0$，Alice 会拿走第一张，Bonnie 拿走第二张，贡献为 $v_A$。
3. $v_A\le0,v_B>0$，同理，贡献为 $-v_B$。
4. $v_A>0,v_B>0$，这个东西和 $a_1+b_1<a_2+b_2$ 是矛盾的，证明简单。
### Code
一个不太简洁但十分自然的实现。
:::success[参考实现]
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Photo {
int a, b;
bool operator<(const Photo& other) const {
return a + b < other.a + other.b;
}
};
priority_queue<Photo> pq;
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int n, ans = 0; cin >> n;
for (int i = 1; i <= n; i ++) {
int a1, b1, a2, b2; cin >> a1 >> b1 >> a2 >> b2;
if (a1 + b1 >= a2 + b2) { pq.push({a1, b1}), pq.push({a2, b2}); }
else {
int vA = a1 - b2, vB = b1 - a2;
if (vA > 0 && vB <= 0) ans += vA;
else if (vA <= 0 && vB > 0) ans += -vB;
}
}
bool alice_turn = true;
while (!pq.empty()) {
Photo top = pq.top();
pq.pop();
if (alice_turn) ans += top.a;
else ans -= top.b;
alice_turn ^= 1;
}
cout << ans << '\n';
}
```
:::