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

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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

# 思路

记忆化搜索 + 分类讨论

# 解法

class Solution {
    public int[] earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
        int m = 1, N = n;
        while (n > 2) {
            n -= n/2;
            m++;
        }
        int[][][][] dp = new int[firstPlayer+1][secondPlayer+1][m+1][];
        return dfs(1, firstPlayer, secondPlayer, dp, N, m);
    }
    private int[] dfs(int p, int f, int s, int[][][][] dp, int n, int m) {
        if (p >= m) return new int[]{p, p};
        if (s == (n+1 - f)) dp[f][s][p] = new int[]{p, p};
        if (dp[f][s][p] != null) return dp[f][s][p];
        int[] res = {Integer.MAX_VALUE, Integer.MIN_VALUE};
        // 分类讨论
        int mid = n/2, t = n&1;
        if (s <= mid + t) {
            for (int i = 1; i <= f; i++) {
                int d = s - f;
                for (int j = 1; j <= d; j++) {
                    int[] dfs = dfs(p + 1, i, i + j, dp, n - n / 2, m);
                    res[0] = Math.min(res[0], dfs[0]);
                    res[1] = Math.max(res[1], dfs[1]);
                }
            }
        }
        if (f > mid) {
            int s_ = n + 1 - s, f_ = n + 1 - f;
            for (int i = 0; i < s_; i++) {
                int d = f_ - s_ - 1, s1 = i + (s - s_ + 2)/2;
                for (int j = 0; j <= d; j++) {
                    int f1 = i + j + (f - f_ + 2)/2;
                    int[] dfs = dfs(p + 1, f1, s1, dp, n - n / 2, m);
                    res[0] = Math.min(res[0], dfs[0]);
                    res[1] = Math.max(res[1], dfs[1]);
                }
            }
        }
        if (f <= mid && s > mid + t) {
            int s_ = n + 1 - s;
            if (s_ < f) {
                for (int i = 0; i < s_; i++) {
                    int d = f - s_;
                    for (int j = 1; j <= d; j++) {
                        int[] dfs = dfs(p + 1, i + j, i + (s - s_ + 2)/2, dp, n - n / 2, m);
                        res[0] = Math.min(res[0], dfs[0]);
                        res[1] = Math.max(res[1], dfs[1]);
                    }
                }
            }
            if (s_ > f) {
                for (int i = 1; i <= f; i++) {
                    int d = s_ - f - 1;
                    for (int j = 0; j <= d; j++) {
                        int[] dfs = dfs(p + 1, i, i + j + (s - s_ + 2)/2, dp, n - n / 2, m);
                        res[0] = Math.min(res[0], dfs[0]);
                        res[1] = Math.max(res[1], dfs[1]);
                    }
                }
            }
        }
        return dp[f][s][p] = res;
    }
}

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

# 总结

分析出几种情况，然后分别对各个情况实现

#Java