专栏文章

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

CCleverSea
P12458题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioy60ka
此快照首次捕获于
2025/12/03 03:04
3 个月前
此快照最后确认于
2025/12/03 03:04
3 个月前
查看原文
此题 143143 个测试点？恐怖如斯……

题意简述

Alice 和 Bob 在定制冰淇淋，规则如下：
  1. Alice 先选择一种口味（价格数组 AA）。
  2. Bob 接着选择一种蛋筒（价格数组 BB）。
  3. Alice 最后选择一种配料（价格数组 CC）。
冰淇淋总价格 S=Ai+Bj+CkS = A_i + B_j + C_k，得分定义为 ∣S−P∣|S - P|。Alice 的目标是最大化得分，Bob 的目标是最小化得分。双方均采取最优策略，计算最终得分。

思路

一个典型的博弈论题目。

游戏分为三个阶段，采用逆向分析可得：
  1. 首先，当已知 AiA_i 和 BjB_j，Alice 会选择 CkC_k 最大化 ∣Ai+Bj+Ck−P∣|A_i + B_j + C_k - P|。
  2. 然后，当已知 AiA_i，Bob 会选择 BjB_j 最小化 Alice 在第 33 步能获得的最大得分。
  3. 最后，Alice 会选择 AiA_i 最大化 Bob 在第二步中最小化的得分。

形式化地，定义：

  • D=min⁡(C)D = \min(C)，E=max⁡(C)E = \max(C)（配料的最小和最大价格）。
  • 对于固定 AiA_i 和 BjB_j，得分为： f(Ai,Bj)=max⁡(∣Ai+Bj+D−P∣,∣Ai+Bj+E−P∣)f(A_i, B_j) = \max\left(|A_i + B_j + D - P|, |A_i + B_j + E - P|\right)
  • Bob 的目标：g(Ai)=min⁡Bjf(Ai,Bj)g(A_i) = \min_{B_j} f(A_i, B_j)。
  • Alice 的目标：ans=max⁡Aig(Ai)\text{ans} = \max_{A_i} g(A_i)。
此时我们注意到，函数 f(s)f(s)（s=Ai+Bjs = A_i + B_j) 在 ss 的不同区间有不同行为：
  1. s≤P−Es \leq P - E：f(s)=P−s−Df(s) = P - s - D（递减）。
  2. P−E<s<P−DP - E < s < P - D：f(s)=max⁡(P−s−D,s+E−P)f(s) = \max(P - s - D, s + E - P)（先减后增，最小值在 s0=P−D+E2s_0 = P - \frac{D+E}{2}）。
  3. s≥P−Ds \geq P - D：f(s)=s+E−Pf(s) = s + E - P（递增）。

综上，本题策略为：

对于每个 AiA_i：
  1. 计算关键点：
    • key1=P−E−Aikey_1 = P - E - A_i（区间 II 的上界）。
    • key2=P−D−Aikey_2 = P - D - A_i（区间 IIIIII 的下界）。
    • s0=2P−D−E2−Ais_0 = \frac{2P - D - E}{2} - A_i（区间 IIII 的最小值点）。
  2. 在排序后的 BB 数组中搜索候选 BjB_j：
    • 区间 I\mathrm{I}：取 ≤key1\leq key_1 的最大 BjB_j。
    • 区间 III\mathrm{III}：取 ≥key2\geq key_2 的最小 BjB_j。
    • 区间 II\mathrm{II}：取最接近 s0s_0 的两个 BjB_j（左侧最大和右侧最小且在 (key1,key2)(key_1, key_2) 内）。
  3. 计算每个候选 BjB_j 对应的 f(s)f(s)，取最小值作为 g(Ai)g(A_i)。
  4. 答案取所有 g(Ai)g(A_i) 的最大值。

美汁汁（zhıˉr\text{zhīr}）的代码时间~

CPP
#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;
}
其中排序 BB 数组 O(Ylog⁡Y)O(Y \log Y)，遍历 AA 数组，每个元素在 BB 上二分查找 O(log⁡Y)O(\log Y)，XX 个元素 O(Xlog⁡Y)O(X \log Y)，总复杂度 O((X+Y)log⁡Y)O((X + Y) \log Y)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...