
题目描述
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
解法
方法一:记忆化搜索 + 二进制枚举
我们定义一个函数 \(\text{dfs}(l, r, n)\),表示在当前回合中,编号为 \(l\) 和 \(r\) 的运动员在 \(n\) 名运动员中比拼的最早和最晚回合数。
函数 \(\text{dfs}(l, r, n)\) 的执行逻辑如下:
- 如果 \(l + r = n - 1\),说明两名运动员在当前回合中比拼,返回 \([1, 1]\)。
- 如果 \(f[l][r][n] \neq 0\),说明之前已经计算过这个状态,直接返回结果。
- 初始化最早回合数为正无穷大,最晚回合数为负无穷大。
- 计算当前回合中前半部分的运动员数目 \(m = n / 2\)。
- 枚举前半部分的所有可能的胜者组合(使用二进制枚举),对于每一种组合:
- 根据当前组合确定哪些运动员获胜。
- 确定当前回合中编号为 \(l\) 和 \(r\) 的运动员在当前回合中的位置。
- 统计当前回合中编号为 \(l\) 和 \(r\) 的运动员在剩余运动员中的位置,记为 \(a\) 和 \(b\),以及剩余运动员的总数 \(c\)。
- 递归调用 \(\text{dfs}(a, b, c)\),获取当前状态的最早和最晚回合数。
- 更新最早回合数和最晚回合数。
- 将计算结果存储在 \(f[l][r][n]\) 中,并返回最早和最晚回合数。
答案为 \(\text{dfs}(\text{firstPlayer} - 1, \text{secondPlayer} - 1, n)\)。
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 | @cache
def dfs(l: int, r: int, n: int):
if l + r == n - 1:
return [1, 1]
res = [inf, -inf]
m = n >> 1
for i in range(1 << m):
win = [False] * n
for j in range(m):
if i >> j & 1:
win[j] = True
else:
win[n - 1 - j] = True
if n & 1:
win[m] = True
win[n - 1 - l] = win[n - 1 - r] = False
win[l] = win[r] = True
a = b = c = 0
for j in range(n):
if j == l:
a = c
if j == r:
b = c
if win[j]:
c += 1
x, y = dfs(a, b, c)
res[0] = min(res[0], x + 1)
res[1] = max(res[1], y + 1)
return res
class Solution:
def earliestAndLatest(
self, n: int, firstPlayer: int, secondPlayer: int
) -> List[int]:
return dfs(firstPlayer - 1, secondPlayer - 1, n)
|
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
56
57
58
59 | class Solution {
static int[][][] f = new int[30][30][31];
public int[] earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
return dfs(firstPlayer - 1, secondPlayer - 1, n);
}
private int[] dfs(int l, int r, int n) {
if (f[l][r][n] != 0) {
return decode(f[l][r][n]);
}
if (l + r == n - 1) {
f[l][r][n] = encode(1, 1);
return new int[] {1, 1};
}
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
int m = n >> 1;
for (int i = 0; i < (1 << m); i++) {
boolean[] win = new boolean[n];
for (int j = 0; j < m; j++) {
if (((i >> j) & 1) == 1) {
win[j] = true;
} else {
win[n - 1 - j] = true;
}
}
if ((n & 1) == 1) {
win[m] = true;
}
win[n - 1 - l] = win[n - 1 - r] = false;
win[l] = win[r] = true;
int a = 0, b = 0, c = 0;
for (int j = 0; j < n; j++) {
if (j == l) {
a = c;
}
if (j == r) {
b = c;
}
if (win[j]) {
c++;
}
}
int[] t = dfs(a, b, c);
min = Math.min(min, t[0] + 1);
max = Math.max(max, t[1] + 1);
}
f[l][r][n] = encode(min, max);
return new int[] {min, max};
}
private int encode(int x, int y) {
return (x << 8) | y;
}
private int[] decode(int val) {
return new int[] {val >> 8, val & 255};
}
}
|
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
56
57
58
59
60
61
62 | int f[30][30][31];
class Solution {
public:
vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
return dfs(firstPlayer - 1, secondPlayer - 1, n);
}
private:
vector<int> dfs(int l, int r, int n) {
if (f[l][r][n] != 0) {
return decode(f[l][r][n]);
}
if (l + r == n - 1) {
f[l][r][n] = encode(1, 1);
return {1, 1};
}
int min = INT_MAX, max = INT_MIN;
int m = n >> 1;
for (int i = 0; i < (1 << m); i++) {
vector<bool> win(n, false);
for (int j = 0; j < m; j++) {
if ((i >> j) & 1) {
win[j] = true;
} else {
win[n - 1 - j] = true;
}
}
if (n & 1) {
win[m] = true;
}
win[n - 1 - l] = false;
win[n - 1 - r] = false;
win[l] = true;
win[r] = true;
int a = 0, b = 0, c = 0;
for (int j = 0; j < n; j++) {
if (j == l) a = c;
if (j == r) b = c;
if (win[j]) c++;
}
vector<int> t = dfs(a, b, c);
min = std::min(min, t[0] + 1);
max = std::max(max, t[1] + 1);
}
f[l][r][n] = encode(min, max);
return {min, max};
}
int encode(int x, int y) {
return (x << 8) | y;
}
vector<int> decode(int val) {
return {val >> 8, val & 255};
}
};
|
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
56
57
58
59
60
61
62
63
64
65
66
67
68 | var f [30][30][31]int
func earliestAndLatest(n int, firstPlayer int, secondPlayer int) []int {
return dfs(firstPlayer-1, secondPlayer-1, n)
}
func dfs(l, r, n int) []int {
if f[l][r][n] != 0 {
return decode(f[l][r][n])
}
if l+r == n-1 {
f[l][r][n] = encode(1, 1)
return []int{1, 1}
}
min, max := 1<<30, -1<<31
m := n >> 1
for i := 0; i < (1 << m); i++ {
win := make([]bool, n)
for j := 0; j < m; j++ {
if (i>>j)&1 == 1 {
win[j] = true
} else {
win[n-1-j] = true
}
}
if n&1 == 1 {
win[m] = true
}
win[n-1-l] = false
win[n-1-r] = false
win[l] = true
win[r] = true
a, b, c := 0, 0, 0
for j := 0; j < n; j++ {
if j == l {
a = c
}
if j == r {
b = c
}
if win[j] {
c++
}
}
t := dfs(a, b, c)
if t[0]+1 < min {
min = t[0] + 1
}
if t[1]+1 > max {
max = t[1] + 1
}
}
f[l][r][n] = encode(min, max)
return []int{min, max}
}
func encode(x, y int) int {
return (x << 8) | y
}
func decode(val int) []int {
return []int{val >> 8, val & 255}
}
|
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
56
57
58
59
60
61
62
63
64
65 | function earliestAndLatest(n: number, firstPlayer: number, secondPlayer: number): number[] {
return dfs(firstPlayer - 1, secondPlayer - 1, n);
}
const f: number[][][] = Array.from({ length: 30 }, () =>
Array.from({ length: 30 }, () => Array(31).fill(0)),
);
function dfs(l: number, r: number, n: number): number[] {
if (f[l][r][n] !== 0) {
return decode(f[l][r][n]);
}
if (l + r === n - 1) {
f[l][r][n] = encode(1, 1);
return [1, 1];
}
let min = Number.MAX_SAFE_INTEGER;
let max = Number.MIN_SAFE_INTEGER;
const m = n >> 1;
for (let i = 0; i < 1 << m; i++) {
const win: boolean[] = Array(n).fill(false);
for (let j = 0; j < m; j++) {
if ((i >> j) & 1) {
win[j] = true;
} else {
win[n - 1 - j] = true;
}
}
if (n & 1) {
win[m] = true;
}
win[n - 1 - l] = false;
win[n - 1 - r] = false;
win[l] = true;
win[r] = true;
let a = 0,
b = 0,
c = 0;
for (let j = 0; j < n; j++) {
if (j === l) a = c;
if (j === r) b = c;
if (win[j]) c++;
}
const t = dfs(a, b, c);
min = Math.min(min, t[0] + 1);
max = Math.max(max, t[1] + 1);
}
f[l][r][n] = encode(min, max);
return [min, max];
}
function encode(x: number, y: number): number {
return (x << 8) | y;
}
function decode(val: number): number[] {
return [val >> 8, val & 255];
}
|