题解：P12458 [JOI2025 预选赛 R2] 冰淇淋
此题
题意简述
Alice 和 Bob 在定制冰淇淋，规则如下：
- Alice 先选择一种口味（价格数组
A ）。 - Bob 接着选择一种蛋筒（价格数组
B ）。 - Alice 最后选择一种配料（价格数组
C ）。
冰淇淋总价格
思路
一个典型的博弈论题目。
游戏分为三个阶段，采用逆向分析可得：
- 首先，当已知
A_i 和B_j ，Alice 会选择C_k 最大化|A_i + B_j + C_k - P| 。 - 然后，当已知
A_i ，Bob 会选择B_j 最小化 Alice 在第3 步能获得的最大得分。 - 最后，Alice 会选择
A_i 最大化 Bob 在第二步中最小化的得分。
形式化地，定义：
-
- 对于固定
A_i 和B_j ，得分为：f(A_i, B_j) = \max\left(|A_i + B_j + D - P|, |A_i + B_j + E - P|\right) - Bob 的目标：
g(A_i) = \min_{B_j} f(A_i, B_j) 。 - Alice 的目标：
\text{ans} = \max_{A_i} g(A_i) 。
此时我们注意到，函数
s \leq P - E ：f(s) = P - s - D （递减）。P - E < s < P - D ：f(s) = \max(P - s - D, s + E - P) （先减后增，最小值在s_0 = P - \frac{D+E}{2} ）。s \geq P - D ：f(s) = s + E - P （递增）。
综上，本题策略为：
对于每个
-
计算关键点：
-
-
在排序后的
B 数组中搜索候选B_j ：- 区间
\mathrm{I} ：取\leq key_1 的最大B_j 。 - 区间
\mathrm{III} ：取\geq key_2 的最小B_j 。 - 区间
\mathrm{II} ：取最接近s_0 的两个B_j （左侧最大和右侧最小且在(key_1, key_2) 内）。
- 区间
-
计算每个候选
B_j 对应的f(s) ，取最小值作为g(A_i) 。 -
答案取所有
g(A_i) 的最大值。
美汁汁（\text{zhīr} ）的代码时间~
#include <bits/stdc++.h>
#define Code using
#define by namespace
#define CleverSea std
Code by CleverSea;
const int N = 2e5 + 10;
long long A[N], B[N], C[N];
int main() {
long long X, Y, Z, P;
scanf("%lld %lld %lld %lld", &X, &Y, &Z, &P);
for (int i = 0; i < X; i++) {
scanf("%lld", &A[i]);
}
for (int i = 0; i < Y; i++) {
scanf("%lld", &B[i]);
}
for (int i = 0; i < Z; i++) {
scanf("%lld", &C[i]);
}
sort(B, B + Y);
// 计算配料的最小值D和最大值E
long long minC = C[0], maxC = C[0];
for (int i = 1; i < Z; i++) {
if (C[i] < minC) minC = C[i];
if (C[i] > maxC) maxC = C[i];
}
long long ans = 0;
// 遍历每种口味
for (int i = 0; i < X; i++) {
long long key1 = P - maxC - A[i]; // 区间I上界
long long key2 = P - minC - A[i]; // 区间III下界
vector<long long> cf; // 存储候选得分
// 候选1：区间I中最大的Bj（<=key1）
int pos1 = upper_bound(B, B + Y, key1) - B;
if (pos1 > 0) {
long long Bj = B[pos1 - 1];
long long s = A[i] + Bj;
long long fv1 = llabs(s + minC - P);
long long fv2 = llabs(s + maxC - P);
long long fv = max(fv1, fv2);
cf.push_back(fv);
}
// 候选2：区间III中最小的Bj（>=key2）
int pos3 = lower_bound(B, B + Y, key2) - B;
if (pos3 < Y) {
long long Bj = B[pos3];
long long s = A[i] + Bj;
long long fv1 = llabs(s + minC - P);
long long fv2 = llabs(s + maxC - P);
long long fv = max(fv1, fv2);
cf.push_back(fv);
}
// 计算区间II的理想点s0
double s0v = (2.0 * P - minC - maxC) / 2 - A[i];
// 候选3：区间II中小于等于s0v的最大Bj
long long flov = (long long)floor(s0v);
int posl = upper_bound(B, B + Y, flov) - B;
if (posl > 0) {
long long can = B[posl - 1];
if (can > key1 && can < key2) { // 在开区间内
long long s = A[i] + can;
long long fv = max(llabs(s + minC - P), llabs(s + maxC - P));
cf.push_back(fv);
}
}
// 候选4：区间II中大于等于s0v的最小Bj
long long ceiv = (long long)ceil(s0v);
int posh = lower_bound(B, B + Y, ceiv) - B;
if (posh < Y) {
long long can = B[posh];
if (can > key1 && can < key2) { // 在开区间内
long long s = A[i] + can;
long long fv = max(llabs(s + minC - P), llabs(s + maxC - P));
cf.push_back(fv);
}
}
// 确保候选列表非空（理论上不会为空，但还是检查一下）
if (!cf.empty()) {
long long minv = *min_element(cf.begin(), cf.end());
if (minv > ans) {
ans = minv;
}
}
}
printf("%lld\n", ans);
return 0;
}其中排序