棋盒盖塞爆游戏胜负判断题解

一、问题核心分析

题目本质是模拟黑白双方轮流提子并累计棋子数量，判断哪一方先出现“累计棋子数严格大于棋盒盖容量M”的情况，先触发该条件的一方输掉比赛，另一方获胜；若全程未触发则为平局。

核心关键点：

1. 落子顺序：黑方先行（第1手），之后黑白交替，即第i手的执棋方为“黑方（i为奇数）”或“白方（i为偶数）”。
2. 提子累计：每手棋提走的棋子数a_i需累加到当前执棋方的棋盒盖中。
3. 失败条件：当前执棋方累加后，棋盒盖中的棋子数严格大于M，则该方失败，另一方获胜。
4. 后续无效：一旦某方触发失败条件，比赛结果已确定，后续操作无需再考虑。

二、算法原理

采用模拟遍历策略，步骤如下：

1. 初始化两个变量分别记录黑方和白方棋盒盖中的累计棋子数（数组a，a[0]对应白方，a[1]对应黑方，通过异或切换执棋方）。
2. 遍历每一手棋：
   • 确定当前执棋方（用fg标记，0为白方，1为黑方，初始为0，每轮异或1切换）。
   • 将当前手的提子数a_i累加到对应执棋方的累计值中。
   • 检查累计值是否严格大于M：若满足，直接输出另一方为获胜者并结束程序。
3. 遍历完所有手棋后，若未出现任何一方累计值超M的情况，输出“Draw”表示平局。

该算法的核心优势是线性时间复杂度，无需额外空间存储所有提子数，边读边处理，高效适配数据规模。

三、完整代码

#include <bits/stdc++.h>
using namespace std;
int a[2], n, m;
string win[2] = {"White", "Black"};
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;

    for (int i = 1, fg = 0, tp; i <= n; i++, fg ^= 1) {
        cin >> tp, a[fg] += tp;

        if (a[fg] > m)
            return cout << win[fg], 0;
    }

    cout << "Draw";
}

四、代码关键步骤解析

1. 输入优化：使用ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);关闭输入输出同步，加速大数据量下的读写速度，适配n≤1e5的约束。
2. 变量定义：
   • a[2]：a[0]存储白方累计提子数，a[1]存储黑方累计提子数。
   • win[2]：结果映射数组，win[fg]表示“当前执棋方fg失败时的获胜者”（如fg=1为黑方失败，获胜者为win[1]即White）。
   • fg：执棋方标记，初始为0（对应第1手黑方？此处需注意逻辑对应：第1手i=1，fg初始为0，循环中先处理提子，再切换fg。实际逻辑为：i=1（黑方）→fg=0，处理后fg异或为1；i=2（白方）→fg=1，处理后异或为0，以此类推。win数组的映射关系已正确匹配该逻辑）。
3. 遍历处理：
   • 循环i从1到n，每轮读取当前手的提子数tp，累加到a[fg]。
   • 立即检查a[fg] > m：若成立，输出对应的获胜者并直接退出程序（无需处理后续手）。
4. 平局处理：若循环正常结束（所有手均未触发失败条件），输出“Draw”。

五、复杂度分析

• 时间复杂度：$O(n)$。仅需遍历n手棋，每手操作均为$O(1)$（读取、累加、判断），完全适配$n≤1e5$的最大数据规模。
• 空间复杂度：$O(1)$。仅使用固定大小的数组和变量，不随输入规模变化，空间效率极高。