E2. Game with Marbles (Hard Version) - 题解

比赛与标签

比赛: Codeforces Round 916 (Div. 3) 标签: games, greedy, sortings 难度: *1400

题目大意喵~

最近，爱丽丝和鲍勃得到了一堆很漂亮的弹珠，一共有 n 种不同的颜色，呐。对于第 i 种颜色，爱丽丝有 a[i] 个，鲍勃有 b[i] 个。

他们想出了一个游戏来决定这些弹珠的归属，规则是这样的说：

爱丽丝先手，然后两人轮流操作。
轮到某个玩家时，他/她必须选择一种颜色 i，前提是当前双方都至少拥有一个该颜色的弹珠。
该玩家丢弃一个颜色 i 的弹珠，而对手则必须丢弃掉所有颜色 i 的弹珠。
当再也找不到满足条件（双方都拥有）的颜色时，游戏结束。

游戏的得分是游戏结束时，爱丽丝剩余的弹珠总数减去鲍勃剩余的弹珠总数。爱丽丝的目标是让这个分数尽可能高（最大化），而鲍勃则希望这个分数尽可能低（最小化）。

假设两个小家伙都绝顶聪明，总能做出最优选择，我们需要计算出游戏的最终得分是多少，喵~

思路分析喵~

这道题看起来像是一个博弈论问题，但直接用极小化极大搜索的话状态太多了，肯定会超时的说。所以我们得找找有没有什么捷径，比如贪心策略，呐！

核心思想: 这道题的核心是一个贪心策略。我们需要找到一个标准来衡量每种颜色对于两位玩家的“价值”或“重要性”，然后根据这个标准来决定玩家的最优选择。
关键观察:
- 首先，我们来分析一下一次操作会发生什么，喵~
  - 如果轮到爱丽丝选择颜色 i：她失去 1 个 a[i]，鲍勃失去所有 b[i]。游戏结束后，在颜色 i 上，爱丽丝拥有 a[i] - 1 个，鲍勃拥有 0 个。对最终得分的贡献就是 (a[i] - 1) - 0 = a[i] - 1。
  - 如果轮到鲍勃选择颜色 i：他失去 1 个 b[i]，爱丽丝失去所有 a[i]。游戏结束后，在颜色 i 上，爱丽丝拥有 0 个，鲍勃拥有 b[i] - 1 个。对最终得分的贡献就是 0 - (b[i] - 1) = 1 - b[i]。
- 游戏一共有 n 种颜色，每种颜色在游戏中只会被选择一次（因为一旦被选，其中一方的该颜色弹珠就清零了），所以整个游戏会进行 n 轮。爱丽丝先手，她会进行第 1, 3, 5, ... 轮操作；鲍勃会进行第 2, 4, 6, ... 轮操作。
- 现在关键问题来了：轮到一位玩家时，他应该选哪种颜色呢？让我们思考一下，对于一种颜色 i，由谁来操作，结果的差异有多大呢？
  - 爱丽丝操作，得分贡献 a[i] - 1。
  - 鲍勃操作，得分贡献 1 - b[i]。
  - 两者的差距是 (a[i] - 1) - (1 - b[i]) = a[i] + b[i] - 2。
- 这个 a[i] + b[i] - 2 的差值，可以看作是“爱丽丝抢到这次操作权”相对于“被鲍勃抢到”所能获得的额外优势。a[i] + b[i] 的值越大，说明这种颜色的弹珠总数越多，操作权归谁的影响就越大，也就是“赌注”越大！
- 既然两个人都很聪明，他们肯定都会去争夺“赌注”最大的颜色。爱丽丝想抢到它来获得 a[i]-1 的高收益，鲍勃也想抢到它，从而让爱丽丝只能得到 1-b[i] 的低收益（甚至是负收益）。
算法流程: 基于上面的观察，一个清晰的贪心策略就浮出水面了，的说喵~
1. 对所有颜色，计算它们的“赌注”大小，也就是 a[i] + b[i] 的值。
2. 将所有 n 种颜色按照 a[i] + b[i] 的值从大到小进行排序。
3. 因为爱丽丝先手，她肯定会选择当前“赌注”最大的颜色进行操作。然后鲍勃会在剩下的颜色里选择“赌注”最大的。他们会轮流从这个排好序的列表的头部取走颜色。
4. 所以，我们只需要遍历这个排序后的颜色列表：
  - 对于列表里第 1, 3, 5, ... 个颜色（也就是下标为 0, 2, 4, ...），这是爱丽丝的选择。我们将 a[i] - 1 加入总分。
  - 对于列表里第 2, 4, 6, ... 个颜色（也就是下标为 1, 3, 5, ...），这是鲍勃的选择。我们将 1 - b[i] 加入总分。
5. 把所有轮次的得分贡献加起来，就是最终的答案啦！

代码实现

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<long long> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    // 创建一个vector来存储每种颜色的 {总和, 原始索引}，喵~
    // 这样排序后还能找到原始的a[i]和b[i]
    vector<pair<long long, int>> v;
    for (int i = 0; i < n; i++) {
        v.push_back({a[i] + b[i], i});
    }

    // 按照 a[i] + b[i] 的和从大到小排序，这就是我们的贪心标准！
    sort(v.begin(), v.end(), [](const pair<long long, int>& p1, const pair<long long, int>& p2) {
        return p1.first > p2.first;
    });

    long long score = 0;
    // 遍历排序后的颜色列表，轮流计算得分贡献
    for (int i = 0; i < n; i++) {
        int original_idx = v[i].second; // 获取该颜色在输入时的原始索引
        
        // i是排序后列表的索引。i为偶数时(0, 2, 4...)，轮到爱丽丝
        if (i % 2 == 0) { 
            // 爱丽丝的回合，她拿走这个“赌注”最大的颜色
            score += a[original_idx] - 1;
        } else { // i为奇数时(1, 3, 5...)，轮到鲍勃
            // 鲍勃的回合，他拿走剩下“赌注”最大的颜色
            score += -(b[original_idx] - 1); // 也可以写成 score += 1 - b[original_idx]
        }
    }

    cout << score << '\n';
}

int main() {
    // 加速输入输出，让程序跑得更快一点，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

时间复杂度: O(N log N) 的说。主要的时间开销在于对 n 种颜色按 a[i]+b[i] 的和进行排序。遍历计算分数只需要 O(N) 的时间。所以总的复杂度由排序决定，是 O(N log N)，其中 N 是颜色的数量。
空间复杂度: O(N) 的说。我们需要 O(N) 的空间来存储输入的 a 和 b 数组，以及一个 O(N) 的 vector<pair> 用于排序。

知识点总结

解决这个问题，主要用到了下面这些可爱的知识点，的说喵~

贪心算法 (Greedy Algorithm): 找到问题的最优子结构，每一步都做出当前看起来最好的选择，最终得到全局最优解。这里的贪心标准就是 a[i] + b[i] 的大小。
博弈论 (Game Theory): 理解双方玩家的目标（一个最大化，一个最小化）以及他们都会采取最优策略，是想出贪心策略的基础。
排序 (Sorting): 贪心策略常常需要排序来找到“最”优的那个选项，这道题就是个典型的例子。

希望这篇题解能帮到你，喵~ 如果还有问题，随时可以再来问哦！

E2. Game with Marbles (Hard Version) - 题解 ​

比赛与标签 ​

题目大意喵~ ​

思路分析喵~ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​