「KTSC 2022 R2」寻找魔法珠 题解

问题分析

我们有 $k+1$ 颗珠子（$k$ 颗普通珠 + 1 颗魔法珠），使用 $M$ 个袋子进行检测。这是一个对抗性优化问题 - 我们不知道魔法珠的位置，必须为最坏情况做准备。

每次检测时：

• 魔法珠所在的袋子花费 $A[i] \times j + B[i]$，其中 $j$ 是该袋子中的珠子数
• 其他袋子的珠子消失
• 重复过程直到只剩魔法珠

目标是最小化最坏情况下的总花费。

关键思路：在线负载均衡视角

这个问题可以看作在线负载均衡问题：

• 每次检测相当于将当前珠子集合分配到 $M$ 台"机器"（袋子）上
• 每台机器的成本函数是线性的：$cost = A[i] \times load + B[i]$
• 对手（魔法珠位置）总是选择让我们付出最大成本的机器
• 我们需要设计分配策略来最小化这个最大成本

贪心递推策略

核心观察

对于 $k$ 颗普通珠的情况，最优策略具有以下性质：

1. 袋子排序：优先使用 $A[i] + B[i]$ 较小的袋子
2. 负载均衡：避免让任何一个袋子承担过多珠子
3. 增量优化：$ans[k]$ 可以从 $ans[k-1]$ 递推得到

算法框架

std::vector<long long> find_minimum_costs(int N, std::vector<int> A, std::vector<int> B) {
    xcy::n = N;
    xcy::m = A.size();
    
    // 读入袋子数据
    for (int I = 1; I <= xcy::m; ++I)
        xcy::a[I].first = A[I - 1], xcy::a[I].second = B[I - 1];
    
    xcy::mian();  // 执行核心计算
    std::vector<long long> V;
    
    for (int I = 0; I < N; ++I)
        V.emplace_back(xcy::ans[I]);
    
    return V;
}

贪心递推过程

void mian() {
    // 按成本效率排序袋子
    std::sort(a + 1, a + m + 1, [&](sp A, sp B) {
        return A.fi + A.se < B.fi + B.se;
    });
    
    // 基础情况：1颗普通珠
    ans[1] = a[2].fi + a[2].se;  // 最坏情况选择成本第二低的袋子
    num[1] = num[2] = 1;
    
    // 初始化优先队列：跟踪每个袋子的边际成本
    for (i = 1; i <= m; ++i)
        ins(i);
    
    // 贪心递推：逐步增加珠子数量
    for (i = 2; i < n; ++i) {
        // 最坏情况成本是之前最大值与当前最小边际成本的较大者
        ans[i] = std::max(ans[i - 1], q.top().fi);
        j = q.top().se;
        ++num[j];  // 给边际成本最小的袋子增加一颗珠子
        q.pop();
        ins(j);    // 重新计算该袋子的边际成本
    }
}

边际成本计算

inline void ins(ll I) {
    q.emp((num[I] + 1)*a[I].fi + a[I].se + ans[num[I]], I);
}

边际成本 = 给袋子 $I$ 增加一颗珠子后的最坏情况总成本：

• (num[I] + 1)*a[I].fi + a[I].se：该袋子检测成本
• + ans[num[I]]：如果魔法珠在其他珠子中，后续检测成本
• 这代表了"如果给这个袋子再加一颗珠子，最坏情况会怎样"

为什么这个贪心策略有效？

对抗性分析

在对抗性设置中，对手总是选择：

$1.$ 让魔法珠在当前检测成本最高的袋子里，或者

$2.$ 让魔法珠在导致后续检测成本最高的珠子里

我们的策略通过以下方式应对：

1. 成本平滑：避免任何袋子成本过高
2. 渐进优化：每次只给边际成本最小的袋子增加负载
3. 前瞻考虑：边际成本包含了后续检测的影响

最优性直觉

• 如果我们让某个袋子负载过重，对手就会选择那个袋子
• 如果我们不均匀分配，对手会选择成本最高的分支
• 贪心策略实现了某种意义的"纳什均衡"

复杂度分析

• 时间复杂度：$O(M \log M + N \log M)$
  • 排序袋子：$O(M \log M)$
  • 优先队列操作：$O(N \log M)$
• 空间复杂度：$O(N + M)$

总结

本题展示了对抗性优化问题的经典解法：

$1.$ 问题重构：将检测过程建模为在线负载均衡

$2.$ 贪心递推：通过边际成本分析逐步构建最优策略

$3.$ 优先队列：高效维护当前最优选择

这种贪心+优先队列的方法在对抗性资源分配问题中非常有效，特别是在成本函数具有良好数学性质（如线性、凸性）时。算法的核心思想是：在不知道对手行动的情况下，通过平衡各选项的"潜在风险"来最小化最坏情况损失。