题解：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'

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;
}

六、复杂度分析

时间复杂度

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

附录、Updates