自动搬运

查看原文

来自洛谷，原作者为

	TemplateClass **

搬运于2025-08-24 23:15:42，当前版本为作者最后更新于2025-05-09 20:47:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

设 Alice、Bob 依次选了口味 $a$、蛋筒 $b$ 和配料 $c$，那么此时得分是 $|a + b + c - P|$。所以对于给定的 $a$ 和 $b$，最终的得分取决于 $c$ 的选择。因为 Alice 最后选，她会选 $c$ 中使得得分最大的那个。那对于 Bob 来说，选 $b$ 的时候要考虑到，不管自己怎么选，Alice 都会在选 $c$ 时最大化得分。所以 Bob 要选一个使得这个最大可能的得分最小的 $b$。

首先我们分析最后选 $c$ 的那一步，显然 Alice 希望总和尽可能地远离 $P$，不难发现只有 $c = \min\{C\}$ 或 $c = \max\{C\}$ 时有可能取到最值，也就是说对于给定的 $a, b$，最终的得分就是

$$\max(|a + b + \min\{C\} - P|, |a + b + \max\{C\} - P|) $$

现在，Bob 在选 $b$ 的时候，面对一个固定的 $a$，他的目标是选择一个 $b$，使得这个式子尽可能小。利用绝对值的几何含义，显然如果希望这两个式子的最大值最小，两边的 $a + b + \min\{C\}$ 和 $a + b + \max\{C\}$ 要尽可能对称地分布在 $P$ 的两侧，也就是说

$$b = -\frac{1}{2}[(a + \min\{C\} - P) + (a + \max\{C\} - P)] $$

也就是

$$b = P - a - \frac{1}{2}(\min\{C\} + \max\{C\})$$

于是我们先对 $B$ 进行排序，然后枚举 $a$，对于每个 $a$，二分得到 $B$ 中离上式最近的值，然后更新一下即可，时间复杂度 $O((X + Y) \log Y)$。

#include<iostream>
#include<algorithm>

constexpr int N = 2e5 + 5;
int x, y, z, p, a[N], b[N], c[N], max = -1;

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0), std::cout.tie(0);
	
	std::cin >> x >> y >> z >> p;
	for(int i = 1; i <= x; ++i) std::cin >> a[i];
	for(int i = 1; i <= y; ++i) std::cin >> b[i];
	for(int i = 1; i <= z; ++i) std::cin >> c[i];
	int cmin = *std::min_element(c + 1, c + z + 1);
	int cmax = *std::max_element(c + 1, c + z + 1);
	std::sort(b + 1, b + y + 1);
	for(int i = 1; i <= x; ++i) {
		double bp = p - (cmin + cmax) / 2. - a[i]; int c;
		int P = std::lower_bound(b + 1, b + y + 1, bp) - b;
		if(P == 1) c = b[1]; else if(P == y + 1) c = b[y];
        else c = (b[P] - bp < bp - b[P - 1] ? b[P] : b[P - 1]);
		int s1 = std::abs(a[i] + c + cmin - p);
		int s2 = std::abs(a[i] + c + cmax - p);
		max = std::max(max, std::max(s1, s2));
	}
	std::cout << max << "\n";
	
	return 0;
}