M - Monopoly - 题解

喵~ 各位热爱算法的小伙伴们，大家好呀！我是你们的朋友，我小助手~ 今天我们要一起攻略的这道题目叫做 "Monopoly"，是一个非常有趣的博弈策略问题哦！别看它规则简单，里面可藏着不少小巧思呢。让我们一起摇摇尾巴，开动脑筋，把它拿下吧！

标签与难度

标签: 搜索, 记忆化搜索, 动态规划, 状态压缩, 博弈论

难度: 2100

题目大意喵~

简单来说，就是博博要和 $N$ 个玩家玩游戏。这 $N$ 个玩家分别有 $a_1, a_2, \dots, a_N$ 枚金币。博博自己没有金币，但他有无限张“均衡卡”。

这种卡片的功能是：

选择一个非空的玩家子集 $S$ 。
计算这些被选中玩家的平均金币数，并向下取整，得到 $T = \lfloor \frac{\sum_{i \in S} a_i}{|S|} \rfloor$ 。
将所有被选中玩家（即所有 $i \in S$ ）的金币数都变成 $T$ 。

博博可以使用任意多次“均衡卡”，他的目标是让所有 $N$ 个玩家中，金币数量最多的那个人，其金币数尽可能少。我们要帮博博算出这个可能的最小最大值是多少，喵~

输入：玩家数量 $N$ 和他们各自的金币数 $a_i$ 。输出：操作后可能实现的最小的最大金币数。

举个例子：如果有5个玩家，金币是 {4, 6, 2, 7, 5}，答案是 3。

解题思路分析

这道题的目标是最小化最大值，看起来有点复杂，我们来一步步拆解它，就像猫咪拆毛线球一样，喵~

最终状态的猜想

首先，我们来思考一下，经过一系列操作后，最终的局面会是什么样的呢？假设我们已经达到了最优状态，玩家们的金币数是 ${b_1, b_2, \dots, b_N}$ ，其中最大值是 $M$ 。

这时候，会不会存在一个玩家的金币数 $b_j < M$ 呢？如果存在，我们就可以把所有金币数为 $M$ 的玩家，以及这个金币数小于 $M$ 的玩家 $b_j$ 选作一个集合 $S$ 来使用均衡卡。这个集合的平均值一定会严格小于 $M$ ，那么向下取整后的新值 $T$ 也必然小于等于 $M-1$ 。这样一来，原来金币数为 $M$ 的玩家，他们的金币都减少了，而新的最大值也一定不会超过原来的 $M$ 。通过这种方式，我们似乎总能让最大值进一步减小。

这个推理告诉我们一个非常重要的结论：最终的最优状态，一定是所有玩家的金币数都相等！ 也就是说，我们最终要达到的目标状态是 {C, C, C, ..., C}。我们的任务就变成了找到那个最小的可能的 $C$ 。

搜索！搜索！

既然目标是找到一个最终状态，这很自然地引导我们向搜索的方向思考。我们可以把每种金币的分布情况看作一个“状态”，使用均衡卡就是从一个状态转移到另一个状态。我们要做的，就是从初始状态出发，找到一条通往某个“全员相等”状态的路径，并且这个最终的数值 $C$ 是所有可能路径中最小的。

这不就是经典的状态空间搜索嘛！我们可以用深度优先搜索（DFS）来探索所有可能的状态。

状态压缩与优化

直接用 (a_1, a_2, ..., a_N) 作为状态，当 $N$ 很大的时候，状态空间会爆炸的！必须进行优化，不然我的小脑袋瓜就要过热啦~

优化1：状态归一化

我们观察到，如果把所有玩家的金币都增加或减少一个相同的数量 $k$ ，那么均衡卡的计算结果也会相应地增加或减少 $k$ 。

\lfloor \frac{\sum_{i \in S} (a_i+k)}{|S|} \rfloor = \lfloor \frac{\sum_{i \in S} a_i + |S|k}{|S|} \rfloor = \lfloor \frac{\sum_{i \in S} a_i}{|S|} \rfloor + k

这意味着，我们可以把所有人的金币数都减去当前所有玩家中的最小值 min_a，然后对这些相对金币数 {a_1-min_a, a_2-min_a, ...} 进行求解。如果我们求出这个相对问题的最优解是 C_relative，那么原问题的最优解就是 C_relative + min_a。

通过这个操作，我们状态数组中总会有一个 0，这能大大减少不同状态的数量，也方便我们对状态进行唯一的表示（比如排序后）。

优化2：记忆化

在搜索过程中，我们可能会多次遇到同一个状态。为了避免重复计算，我们可以用一个 map 或者哈希表来记录已经计算过的状态和它的最优解。这就是记忆化搜索，喵~ 每次进入一个新的状态，先查表，如果已经算过了，就直接返回答案。

优化3：剪掉不必要的枝叶 (关键观察)

操作简化：虽然题目允许我们选择任意大小的子集 $S$ ，但经过分析和观察AC代码可以发现，一个惊人的事实是：我们似乎只需要考虑对两个玩家组成的子集（即玩家对）进行操作就足够了！这可能意味着任何对大子集的操作，其效果都可以通过一系列更优或等价的对子操作来达成。这是一个非常强的剪枝，它将每次状态转移的可能性从 $2^N-1$ 种减少到了 $N(N-1)/2$ 种。
规模限制：另一个更神秘的观察是，当玩家数量 $N$ 超过一个很小的数（比如6）时，问题的解似乎只和金币数最少的那6个玩家有关。所以，我们可以大胆地假设，当 $N>6$ 时，我们只需要考虑金币最少的那6个玩家即可。这可能是因为金币数量 $a_i$ 的上限（50）比较小，当玩家数量增多时，多余的玩家要么金币数太大，可以通过与小数的平均来有效降低，要么就是他们之间的交互对最小化最终结果的影响不大。

虽然这两个观察的严格数学证明很复杂，但在解题竞赛中，相信AC代码的共同特征往往是通往正确答案的捷径，呐！

算法流程总结

结合以上分析，我们的解题策略就清晰了：

读取输入 $N$ 和玩家金币 $a_i$ 。
对金币数组 a 进行升序排序。
如果 $N > 6$ ，则只保留前6个（最小的）玩家，即 N = 6。
编写一个递归函数 dfs(vector<int> currentState)，并使用 map<vector<int>, int> memo 进行记忆化。
在 dfs 函数内部： a. 归一化：找到当前状态的最小值 min_val，所有元素减去 min_val 得到归一化状态 normalizedState。 b. 查表：在 memo 中查找 normalizedState。如果找到，直接返回 memo[normalizedState] + min_val。 c. 基线条件：如果所有玩家金币数相同（即归一化后全为0），说明我们到达了一个终点。这个终点的金币值就是 min_val，直接返回它。 d. 递归探索：遍历所有玩家对 (i, j)。计算平均值 avg = (currentState[i] + currentState[j]) / 2，生成新状态 nextState，然后递归调用 dfs(nextState)。在所有可能的后续状态中，取一个最小的返回结果 min_result。 e. 存表：将当前状态的计算结果存入 memo。注意，我们存的是相对值，即 memo[normalizedState] = min_result - min_val。 f. 返回：返回 min_result。
初始调用 dfs(a)，输出结果。

这样，我们就能在可接受的时间内，找到那个神奇的最小共同富裕值啦！

代码实现

这是我根据上面的思路，精心重构的一份代码~ 希望能帮助你更好地理解这个过程，喵！

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map>

// 使用 map 来存储已经计算过的状态，避免重复搜索
// key 是归一化后的状态（一个vector），value 是该状态能达到的最小最终值（相对值）
std::map<std::vector<int>, int> memo;

int solve(std::vector<int> players) {
    // 排序保证状态的唯一性
    std::sort(players.begin(), players.end());

    // --- 状态归一化 ---
    // 找到当前状态的最小值
    int min_val = players[0];
    // 如果所有玩家金币都一样，说明到达了最终状态，返回该值
    if (players.back() == min_val) {
        return min_val;
    }

    // 创建归一化后的状态向量
    std::vector<int> normalized_players = players;
    for (int& p : normalized_players) {
        p -= min_val;
    }

    // --- 记忆化搜索 ---
    // 查找备忘录中是否已有当前归一化状态的解
    if (memo.count(normalized_players)) {
        // 如果有，直接返回之前计算好的结果（相对值 + 本次归一化的基准值）
        return memo[normalized_players] + min_val;
    }

    // --- 递归探索 ---
    // 初始化当前能达到的最小值为一个很大的数
    int min_reachable_val = 1e9;
    int n = players.size();

    // 遍历所有玩家对 (i, j)
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            // 如果两个玩家金币一样，操作无意义，跳过
            if (players[i] == players[j]) {
                continue;
            }

            // 创建下一个状态
            std::vector<int> next_players = players;
            int avg = (players[i] + players[j]) / 2;
            next_players[i] = avg;
            next_players[j] = avg;

            // 递归地求解新状态能达到的最优解
            min_reachable_val = std::min(min_reachable_val, solve(next_players));
        }
    }
    
    // --- 记录结果 ---
    // 将当前归一化状态的最优解（相对值）存入备忘录
    memo[normalized_players] = min_reachable_val - min_val;

    return min_reachable_val;
}

void run_case() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    
    // 对初始金币排序
    std::sort(a.begin(), a.end());
    
    // 关键优化：如果玩家数大于6，只考虑金币最少的6个
    if (n > 6) {
        a.resize(6);
    }

    // 清空上一组测试用例的记忆化数据
    memo.clear();
    std::cout << solve(a) << std::endl;
}

int main() {
    // 优化C++的IO速度
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        run_case();
    }

    return 0;
}

复杂度分析

时间复杂度: $O(\text{S} \times N^2 \times N \log N)$ 这是一个比较粗略的估计，喵~ 这里的 $S$ 是对于 $N \le 6$ 且 $a_i \le 50$ 时，所有可达的、归一化的状态总数。 $N^2$ 是我们选择玩家对的数量，而每次递归调用后对新状态排序需要 $O(N \log N)$ 。由于状态总和是递减的，且有记忆化，实际的运行速度会比这个上界快得多。
空间复杂度: $O(\text{S} \times N)$ 主要开销在于记忆化用的 map。它存储了 $S$ 个状态，每个状态是一个长度为 $N$ 的 vector。

知识点总结

这道题是一个很好的例子，展示了如何将一个看似无从下手的博弈问题，通过一步步的分析和简化，转化为一个可以解决的搜索问题。

问题转化：通过观察操作性质，推断出最优解一定是所有玩家金币数相等的状态。这极大地简化了我们的目标。
状态空间搜索：将问题建模为状态转移图，并使用DFS进行求解。
记忆化搜索：通过存储已解决的子问题答案，避免重复计算，是优化递归搜索的利器。
状态表示与归一化：找到一个等价但更紧凑的状态表示（相对金币数），是压缩状态空间、让记忆化更高效的关键。
剪枝与启发式观察：在复杂问题中，基于问题特性或实验性结论（如本题的 $N \le 6$ 和 pairwise 操作）进行大胆剪枝，有时是让算法可行的不二法门。

希望这篇题解能帮到你！如果还有不明白的地方，随时可以再来问我哦~ 祝大家刷题愉快，天天AC，喵~！

M - Monopoly - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

最终状态的猜想 ​

搜索！搜索！ ​

状态压缩与优化 ​

算法流程总结 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​