最佳运动员的比拼回合
Zhongjun Qiu 元婴开发者

1900. 最佳运动员的比拼回合 [Hard] 题解

暴力解法

Leetcode 1900. 最佳运动员的比拼回合

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

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

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

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

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

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

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
输入: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:

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

提示:

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

思路

1. 核心思想

题目要求我们找出 firstPlayersecondPlayer 可能相遇的 最早最晚 回合。关键在于我们可以操控 firstPlayersecondPlayer 之外所有比赛的结果。这引导我们使用搜索算法来探索所有可能导致两位最佳运动员相遇的比赛进程。

2. 状态定义与搜索

我们可以使用 深度优先搜索 (DFS) 来模拟锦标赛的每一轮。为了定义搜索的状态,我们需要知道在每一轮开始时,哪些选手还留在场上。

  • 状态表示:由于 n 的最大值是 28,我们可以用一个整数的 位掩码 (bitmask) 来表示所有选手的存活状态。例如,一个 n 位的二进制数,如果第 i 位是 0,表示编号为 i+1 的选手仍在比赛中;如果为 1,则表示已被淘汰。

  • DFS 函数:我们可以定义一个 dfs(mask) 函数,它返回从 mask 这个状态(即某些选手已被淘汰)开始,到最后 firstPlayersecondPlayer 相遇所需的最早和最晚回合数。

3. 记忆化搜索

在搜索过程中,我们可能会通过不同的比赛结果(例如,A胜B、C胜D 与 A胜D、C胜B)达到同一个选手集合状态(mask)。为了避免对同一状态进行重复计算,我们采用 记忆化搜索,将每个 mask 对应的计算结果缓存起来。

4. 算法流程

dfs(mask, round) 函数的执行流程如下:

  1. 记忆化检查:检查是否已经计算过当前 mask 的结果。如果已计算,直接返回缓存的结果。

  2. 模拟当前回合

    • 根据 mask 找出当前所有在场的选手,并按编号升序排列。
    • 进行配对:第 1 个在场选手 vs. 最后一个,第 2 个 vs. 倒数第 2 个,以此类推。
  3. 终止条件

    • 在配对过程中,如果 firstPlayersecondPlayer 被分到一组,意味着他们在本回合相遇。这是搜索的一条路径的终点。返回 {round, round}
  4. 递归探索

    • 如果两位最佳选手没有在本轮相遇,他们将各自战胜对手晋级。
    • 对于其他 m 场比赛,每场比赛都有两种可能的结果(A胜B 或 B胜A)。因此,本轮总共有 2^m 种不同的晋级结果。
    • 遍历这 2^m 种可能性:
      • 对于每一种结果,生成下一轮的 new_mask(将本轮的失败者标记为淘汰)。
      • 递归调用 dfs(new_mask, round + 1),获取后续比赛的最早和最晚回合。
      • 在所有 2^m 个递归结果中,取最小的最早回合数和最大的最晚回合数,作为当前 mask 状态的结果。
  5. 缓存并返回:将计算出的 {min_val, max_val} 存入缓存,并返回。

初始调用为 dfs(0, 1),表示在第 1 轮,所有选手都未被淘汰。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

class Solution {
public:
vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
firstPlayer -= 1, secondPlayer -= 1;
int m = 1 << n;
unordered_map<ll, ll> dp;
function<pii(int,int,int)> dfs = [&](int state, int round, int num) -> pii {
if (dp.find(state) != dp.end()) {
ll cv = dp[state];
ll cmi = cv >> 32, cma = cv & ((1LL << 32) - 1);
return {cmi, cma};
}
vector<pii> cur;
for (int _ = 0, i = 0, j = n - 1; _ < num / 2; _++, ++i, --j) {
while (i < j && (state >> i & 1) == 1) ++i;
while (i < j && (state >> j & 1) == 1) --j;
if (i >= j) {
break;
}
if (i == firstPlayer && j == secondPlayer) {
return {round, round};
}
cur.push_back({i, j});
}
int cminv = 1e9, cmaxv = 1;
for (int i = 0;i < (1 << (num / 2)); i++) {
int nxt = state;
for (int j = 0;j < num / 2;j++) {
if (cur[j].first == firstPlayer || cur[j].first == secondPlayer) {
nxt |= (1 << cur[j].second);
continue;
}
if (cur[j].second == firstPlayer || cur[j].second == secondPlayer) {
nxt |= (1 << cur[j].first);
continue;
}
if (i >> j & 1) nxt |= (1 << cur[j].first);
else nxt |= (1 << cur[j].second);
}
pii res = dfs(nxt, round + 1, num - num / 2);
cminv = min(cminv, res.first), cmaxv = max(cmaxv, res.second);
}
dp[state] = (((ll)cminv) << 32) | cmaxv;
return {cminv, cmaxv};
};
pii ans = dfs(0, 1, n);
return {ans.first, ans.second};
}
};

复杂度

  • 时间复杂度: O(2n ⋅ n)
    • 状态由存活选手的 mask 定义,总共有 2n 种状态。
    • 对于每个状态,我们需要 O(n) 的时间来确定在场选手和配对。然后,我们会遍历所有可能的比赛结果,这看似会导致巨大的分支因子。
    • 然而,由于使用了记忆化,每个状态只会被完整计算一次。因此,总时间复杂度是状态数乘以单次计算的开销。虽然实际可达到的状态数远小于 2n,但这是一个宽松的上限。
  • 空间复杂度: O(2n)
    • 空间主要用于记忆化缓存 memo,在最坏情况下可能需要存储所有 2n 个状态的结果。
    • 递归调用的栈深度最多为 O(log n)
 REWARD AUTHOR
 Comments
Comment plugin failed to load
Loading comment plugin