最佳运动员的比拼回合

难度: Hard

n 名运动员参与一场锦标赛，所有运动员站成一排，并根据 最开始的 站位从 1 到 n 编号（运动员 1 是这一排中的第一个运动员，运动员 2 是第二个运动员，依此类推）。

锦标赛由多个回合组成（从回合 1 开始）。每一回合中，这一排从前往后数的第 i 名运动员需要与从后往前数的第 i 名运动员比拼，获胜者将会进入下一回合。如果当前回合中运动员数目为奇数，那么中间那位运动员将轮空晋级下一回合。

例如，当前回合中，运动员 1, 2, 4, 6, 7 站成一排
- 运动员 1 需要和运动员 7 比拼
- 运动员 2 需要和运动员 6 比拼
- 运动员 4 轮空晋级下一回合

每回合结束后，获胜者将会基于最开始分配给他们的原始顺序（升序）重新排成一排。

编号为 firstPlayer 和 secondPlayer 的运动员是本场锦标赛中的最佳运动员。在他们开始比拼之前，完全可以战胜任何其他运动员。而任意两个其他运动员进行比拼时，其中任意一个都有获胜的可能，因此你可以裁定谁是这一回合的获胜者。

给你三个整数 n、firstPlayer 和 secondPlayer 。返回一个由两个值组成的整数数组，分别表示两位最佳运动员在本场锦标赛中比拼的最早回合数和最晚回合数。

示例 1：

输入：n = 11, firstPlayer = 2, secondPlayer = 4
输出：[3,4]
解释：
一种能够产生最早回合数的情景是：
回合 1：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
回合 2：2, 3, 4, 5, 6, 11
回合 3：2, 3, 4
一种能够产生最晚回合数的情景是：
回合 1：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
回合 2：1, 2, 3, 4, 5, 6
回合 3：1, 2, 4
回合 4：2, 4

示例 2：

输入：n = 5, firstPlayer = 1, secondPlayer = 5
输出：[1,1]
解释：两名最佳运动员 1 和 5 将会在回合 1 进行比拼。
不存在使他们在其他回合进行比拼的可能。

提示：

2 <= n <= 28
1 <= firstPlayer < secondPlayer <= n

Submission

运行时间: 40 ms

内存: 16.7 MB

class Solution:
    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:
        @cache
        def f(n,a,b):
            if a+b==n+1:
                return [1,1]
            if a>n//2 and b>n//2:
                a=n+1-a 
                b=n+1-b 
            if a>b:
                a,b=b,a
            if a>n+1-b:
                a,b=n+1-b,n+1-a
            mi=inf 
            ma=0
            low=0
            up=b-a
            if b>(n+1)//2:
                low=b-(n+1)//2
                up=low+n+1-b-a
            for i in range(a):
                for j in range(low,up):
                    x,y=f((n+1)//2,a-i,b-i-j)
                    mi=min(mi,x+1)
                    ma=max(ma,y+1)
            return mi,ma 
        return f(n,firstPlayer,secondPlayer)

Explain

这个题解使用了记忆化搜索的方法。函数f(n, a, b)表示在n个运动员中，编号为a和b的两个最佳运动员比拼的最早和最晚回合数。函数首先处理一些边界情况，然后枚举a和b之间的其他运动员，递归计算子问题的结果，最后返回最早和最晚回合数。通过记忆化搜索避免了重复计算相同子问题，提高了效率。

时间复杂度: O(n^3)

空间复杂度: O(n^2)

class Solution:
    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:
        @cache
        def f(n, a, b):
            # 如果a和b的编号之和等于n+1，说明他们是最后两个运动员，直接比拼，回合数为1
            if a + b == n + 1:
                return [1, 1]
            
            # 如果a和b都在后半部分，可以将问题转化为前半部分的等价问题
            if a > n // 2 and b > n // 2:
                a = n + 1 - a 
                b = n + 1 - b
            
            # 确保a的编号小于b
            if a > b:
                a, b = b, a
            
            # 如果a和n+1-b之间的运动员数量较少，可以交换a和n+1-b，减少枚举次数
            if a > n + 1 - b:
                a, b = n + 1 - b, n + 1 - a
            
            mi = inf 
            ma = 0
            low = 0
            up = b - a
            
            # 确定枚举的范围
            if b > (n + 1) // 2:
                low = b - (n + 1) // 2
                up = low + n + 1 - b - a
            
            # 枚举a和b之间的其他运动员，递归计算子问题的结果
            for i in range(a):
                for j in range(low, up):
                    x, y = f((n + 1) // 2, a - i, b - i - j)
                    mi = min(mi, x + 1)
                    ma = max(ma, y + 1)
            
            return mi, ma
        
        return f(n, firstPlayer, secondPlayer)

Explore

这个假设通常用于简化问题模型，使得某些特定运动员（即最佳运动员）的比较结果可预测，而不需要涉及更复杂的随机或概率计算。这样的设定减少了问题的复杂性，使得可以聚焦于算法逻辑和策略的设计，而不是每个运动员之间的具体比拼结果。

当运动员数目为偶数时，每个回合中所有运动员都可以找到对手进行比拼，因此没有运动员需要轮空。这意味着比赛可以更公平地进行，每位运动员都有相同数量的比赛机会。不存在轮空的情况有助于确保比赛的连续性和公正性，每个回合所有运动员都参与比赛，保持比赛的活跃和竞争性。

在这个问题的上下文中，如果`a + b == n + 1`，这意味着a和b的位置正好是相对的，即一个在赛程的开始，另一个在赛程的结束。例如，如果有5个运动员，第1个和第5个（1 + 5 = 6 = 5 + 1）是对立面。在进行比赛时，按照这种配对方式，他们会在所有其他可能的比拼都完成后才会相遇，因此他们是最后两个进行比赛的运动员。

将运动员a和b的位置调换来保证a < b的主要原因是为了简化问题处理过程。这样做可以减少需要考虑的情况数，使得算法可以统一处理所有情况而无需分别考虑a和b的大小关系。这对于提高代码的可读性和减少错误非常有帮助，同时也简化了递归函数的设计，因为只需要考虑一种情况（a < b）即可。