题解：AT_agc026_f [AGC026F] Manju Game

· · 题解

作者撰写的内容标识：本题解除了提议理解相关内容（这部分由 AI 撰写）均为作者撰写。

一、题意简述

游戏规则

有 N 个盒子从左到右排成一排，第 i 个盒子中有 a_i 个馒头。Sugim（先手）和 Sigma（后手）进行博弈游戏。

游戏规则：

  1. 两人轮流操作，每次操作选择一个未放置棋子的盒子放入自己的棋子。
  2. 相邻限制：必须选择与对手上一次操作相邻的盒子（左右相邻均可）。
  3. 特殊情况：
    • 如果没有满足条件的相邻盒子，可以任选一个未放置的盒子。
    • Sugim 的第一次操作可以任选盒子。
  4. 游戏进行 N 次后结束，每人获得自己棋子所在盒子的所有馒头。

目标：求双方都采用最优策略时，各自能获得多少馒头。

二、核心观察

观察 1：游戏的奇偶性质

关键发现：无论如何游戏，最终被选择的位置具有奇偶交替的性质。

证明思路：

推论：

观察 2：N 为偶数时的简单性

当 N 为偶数时：

三、N 为奇数时的解法

3.1 问题建模

对于 N 为奇数的情况，我们需要更精细的分析。

差值序列的构造：

定义前缀差值序列 s[i]：

s[i] = \begin{cases} s[i - 1] + a[i] & i \bmod 2 = 1 \\ s[i - 1] - a[i] & i \bmod 2 = 0 \end{cases}

其中 s[0] = 0。

物理意义：

3.2 二分答案

目标：找到 Sugim 相对于平均值的最大优势 \delta。

最终答案：

二分范围：\delta \in [0, \text{odd} + \text{even}]。

二分策略：

3.3 Check 函数详解

问题：如何判断是否能让 Sugim 获得至少 \delta 的优势？

贪心 DP 思路：

bool check(int delta) {
    int mn = 0;  // 记录可用的最小前缀和
    for (int i = 1; i <= n; i += 2) {
        if (s[i] - mn >= delta)  // 如果在位置 i 能达到优势 delta
            mn = min(mn, s[i + 1]);  // 更新最小前缀，允许在 i+1 处"转折"
    }
    return s[n] - mn >= delta;  // 最终检查是否达到 delta
}

算法原理：

  1. 状态定义：mn 表示当前可选的最优"起始前缀和"。
  2. 转折点选择：
    • 遍历所有奇数位置 i。
    • 如果 s[i] - \text{mn} \geq \delta，说明从某个"起始点"到 i 能达到优势 \delta。
    • 此时可以选择在 i + 1 处"转折"，即改变后续的奇偶归属。
    • 更新 \text{mn} = \min(\text{mn}, s[i + 1])，为后续提供更优的起始点。
  3. 最终判定：检查 s[n] - \text{mn} \geq \delta。

为什么这样是正确的？

四、算法流程

完整步骤

  1. 输入处理：
    • 读入 N 和数组 a[]。
    • 计算 \text{odd} 和 \text{even}。
    • 构造差值序列 s[]。
  2. N 为偶数时：
    • 如果 N \bmod 2 = 0，直接输出 \max(\text{odd}, \text{even}) 和 \min(\text{odd}, \text{even})。
  3. N 为奇数时：
    • 二分答案 \delta \in [0, \text{odd} + \text{even}]。
    • 对每个 \delta，调用 check(delta) 验证可行性。
    • 找到最大的可行 \delta。
    • 输出 \text{even} + \delta 和 \text{odd} - \delta。

五、代码实现

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fclose fclose(stdin), fclose(stdout)
#define debug(x) cerr << #x << " = " << (x) << endl

int n;
vector<int> a, s;
int odd, even;

bool check(int delta) {
    int mn = 0;
    for (int i = 1; i <= n; i += 2) {
        if (s[i] - mn >= delta)
            mn = min(mn, s[i + 1]);
    }
    return s[n] - mn >= delta;
}

void solve() {
    cin >> n;
    a.resize(n + 5);
    s.resize(n + 5);
    odd = even = 0;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i & 1) {
            odd += a[i];
            s[i] = s[i - 1] + a[i];
        } else {
            even += a[i];
            s[i] = s[i - 1] - a[i];
        }
    }

    if (!(n & 1)) {
        cout << max(odd, even) << " " << min(odd, even) << endl;
        return;
    }

    int l = 0, r = odd + even, delta = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            delta = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    cout << even + delta << " " << odd - delta << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

六、复杂度分析

时间复杂度

空间复杂度

七、样例详解

样例 1

输入：

5
20 100 10 1 10

分析：

  4. 差值序列：
    • s[0] = 0
    • s[1] = 0 + 20 = 20
    • s[2] = 20 - 100 = -80
    • s[3] = -80 + 10 = -70
    • s[4] = -70 - 1 = -71
    • s[5] = -71 + 10 = -61
  5. 二分过程：
    • 初始：l = 0, r = 141
    • 二分得到最大可行 \delta = 19
  6. 最终答案：
    • Sugim = 101 + 19 = 120
    • Sigma = 40 - 19 = 21

输出：120 21

样例 2

输入：

6
4 5 1 1 4 5

分析：

  4. 直接输出：\max(9, 11) = 11，\min(9, 11) = 9。

输出：11 9

八、关键要点总结

核心技巧

  1. 奇偶性质：利用游戏的相邻限制，发现位置的奇偶交替规律。
  2. 差值序列：将问题转化为优势值的计算。
  3. 二分答案：将最优化问题转化为判定问题。
  4. 贪心 DP：通过维护最优前缀和，判断是否能达到目标优势。

易错点

  1. 边界处理：注意 s[i + 1] 的访问，需要预留足够空间。
  2. 奇偶判断：注意区分 N 的奇偶性。
  3. 二分边界：\delta 的上界是 \text{odd} + \text{even}，不是 \max(\text{odd}, \text{even})。

推广

这道题的思想可以推广到其他相邻限制的博弈问题，核心是：

九、参考题目难度及算法标签（仅代表个人观点）

作者原创内容：核心观察、算法详解、代码实现、技巧总结、以及其他解题核心部分。

由 AI 辅助 / 生成的内容大致包括但不限于：题解格式、代码细节讲解、题解思路框架、以及样例分析的具体内容（在作者写完过后提交给 AI 检查过一遍拼写等细节问题）。

附录、Updates