Leetcode每日一题 —— 877. 石子游戏

脑筋急转弯来的，除了结论外还得想想为什么。关于为什么偶数个堆，先手能赢，帮佬友补个不严谨的推导：

把 piles 按偶数下标和奇数下标分组：

偶数下标和：

奇数下标和：

由题目条件知: \mathrm{E}+\mathrm{O}= 石头总和（奇数），因此不可能有 \mathrm{E}=\mathrm{O} ，只有可能 \mathrm{E}>\mathrm{O} 或者 \mathrm{E}<\mathrm{O}。

Alice 先手，可以先取最左边（偶数下标），也可以取最右边（奇数下标），因此 Alice 既可以选择 \mathrm{E} 也可以选择 \mathrm{O} 这一组，那她自然就会选更大的这一组了。

如果选了奇数下标，那么每次轮到 Alice 时选的都可以是奇数下标，反之则都可以是偶数下标。

所以说，Alice 先手必胜。Bob 被做局了啊！

class Solution {

public:

    bool stoneGame(vector<int>& piles) {

        // 假设二人都发挥出最佳水平

        // Alice 先手，且 piles 长度为偶数

        // Alice 可以极力避免 Bob 拿到更多的石头

        // 比如 2 3 10 6, Alice 就可以先取 2，这样 Bob 就选不到 10

        // Alice 总能赢

        return true;

    }

};

先手可以选择不全按奇偶取，但是如果想，可以逼迫后手全取奇/偶，从而必胜

算术评级 6 第 95 场周赛 Q2 难度分 1590

class Solution:

    def stoneGame(self, piles: List[int]) -> bool:

        return True