移除石头游戏

1、题目描述

Alice 和 Bob 在玩一个游戏，他们俩轮流从一堆石头中移除石头，Alice 先进行操作。

• Alice 在第一次操作中移除 恰好 10 个石头。
• 接下来的每次操作中，每位玩家移除的石头数 恰好 为另一位玩家上一次操作的石头数减 1 。
  第一位没法进行操作的玩家输掉这个游戏。

给你一个正整数 n 表示一开始石头的数目，如果 Alice 赢下这个游戏，请你返回 true ，否则返回 false 。

注意：竞赛中，请勿复制题面内容，以免影响您的竞赛成绩真实性。

2、问题分析

1、操作规律：

• Alice 第一次移除 10 个石头。
• 之后每位玩家移除的石头数是 另一位玩家上一次操作的石头数减 1。
• 操作的序列是：10, 9, 8, …, 1（直到无法继续）。

2、游戏结束条件：

• 如果剩余的石头数不足以让当前玩家执行操作，则游戏结束，当前玩家输。

3、目标：

• 确定 Alice 是否能获胜。

3、解题思路

操作序列的总和：

• 操作的数目形成一个递减的序列：10, 9, 8, …, 1。
• 若总和 S=10+9+8+…+1 = $ \frac{10 \times (10 + 1)}{2} $$= 55，当 n>55，两人都无法耗尽石头，Alice 无法赢。
• 若 n≤55，我们需要模拟每一步操作。

模拟游戏：

• 轮流执行操作。
• 每次减去当前所需的石头数。
• 如果剩余的石头数不足以执行操作，则当前玩家输掉比赛。

4、代码实现

class Solution {
public:bool canAliceWin(int n) {int turn = 0; // 0 表示 Alice 的回合, 1 表示 Bob 的回合int currentMove = 10; // 初始操作为 10while (n >= currentMove) {n -= currentMove; // 当前玩家移除石头currentMove--;    // 下次需要移除的石头数减 1turn ^= 1;        // 切换回合}// 如果当前玩家无法操作，判断输赢return turn == 1; // 若 Bob 回合无法操作, Alice 胜利}
};

5、复杂度分析

1. 时间复杂度：
   • 模拟过程最多需要 O(10) 次操作（10 次减法）。
   • 时间复杂度：O(1) 。
2. 空间复杂度：
   • 仅使用常数额外空间。
   • 空间复杂度：O(1) 。