题解：P12458 [JOI2025 预选赛 R2] 冰淇淋

· · 题解

设 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;
}