203 小 Q 和小 X 的游戏

问题描述

小 Q 和小 X 是很好的朋友，她们正在玩一个游戏。她们拿到了一个数组，游戏开始时小 Q 随机选择一个元素作为起点。接着，两人轮流行动，小 Q 先行动。

每次行动时，当前玩家需要选择当前元素左边比它更小的元素，然后移动到该元素，接下来换另一方从这个元素继续移动。如果某一方无法进行合法的移动，则该方输掉游戏。

小 Q 想知道，在双方都采取最优策略的情况下，她最终获胜的概率是多少？请输出分数的最简形式，即分子和分母互素。如果小 Q 必胜，则输出 1/1。如果小 Q 必败，则输出 0/1。

解题思路

因为起点是随机的，那么一共有 $n$ 种可能的起点。对于每个起点，我们可以通过模拟游戏的过程来判断小 Q 是否能获胜。

因为双方都采取最优策略，如果当前位置左边没有比它更小的元素，那么当前玩家必败。否则先手的小 Q 可以直接移动到左边的最小元素获得胜利。因此，我们可以通过统计当前位置左边是否存在比它更小的元素来判断小 Q 是否能获胜。

代码实现

以下是基于上述思路的 Python 代码实现：

from math import gcd

def solution(n: int, a: list) -> str:
    mi = float('inf')
    cnt = 0
    for i in range(n):
        if a[i] > mi:
            cnt += 1
        else:
            mi = a[i]
    # 计算最大公约数，化简分数
    g = gcd(cnt, n)
    return f'{cnt//g}/{n//g}'

if __name__ == '__main__':
    print(solution(5, [3, 1, 5, 4, 3]) == '3/5')
    print(solution(6, [6, 2, 9, 7, 4, 3]) == '2/3')
    print(solution(4, [8, 5, 6, 3]) == '1/4')