class Solution {
public:
vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
}
};
1900. 最佳运动员的比拼回合
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 <= 281 <= firstPlayer < secondPlayer <= n原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 6.6 MB, 提交时间: 2023-10-25 23:44:43
func earliestAndLatest(n, firstPlayer, secondPlayer int) []int {
type pair struct{ min, max int } // 最早回合数和最晚回合数
dp := make([][][]pair, n+1)
for i := range dp {
dp[i] = make([][]pair, n)
for j := range dp[i] {
dp[i][j] = make([]pair, n)
}
}
var f func(n, fi, se int) pair
f = func(n, fi, se int) (ans pair) {
if fi+se == n-1 { // 发生比拼
return pair{1, 1}
}
if fi >= n-1-fi || fi > n-1-se { // 为简化后续枚举过程，在枚举前处理一下两名选手的位置
fi, se = n-1-se, n-1-fi
}
dv := &dp[n][fi][se]
if dv.min > 0 {
return *dv
}
defer func() { *dv = ans }()
ans.min = 1e9
mid := (n + 1) / 2 // 下一轮人数
var next pair
for i := 0; i <= fi; i++ { // 枚举第一名选手左侧保留多少个人
for j := 0; j < min(se, n-1-se)-fi; j++ { // 枚举第一名选手和第二名选手中间保留多少个人
if se < mid { // 两人同侧（处理位置后都位于中间位置左侧）
next = f(mid, i, i+j+1)
} else { // 两人异侧
next = f(mid, i, i+j+1+(se*2-n+1)/2)
}
ans.min = min(ans.min, next.min)
ans.max = max(ans.max, next.max)
}
}
// 加上当前回合数
ans.min++
ans.max++
return
}
res := f(n, firstPlayer-1, secondPlayer-1) // 下标从 0 开始
return []int{res.min, res.max}
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
cpp 解法, 执行用时: 964 ms, 内存消耗: 6.5 MB, 提交时间: 2023-10-25 23:44:20
struct node
{
int a , b;
bool operator <(const node &p)
{
return b < p.b;
}
}player[30];
class Solution {
public:
vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer)
{
srand(time(NULL));
// 根据n的大小设置模拟次数
int N;
if(n <= 10)
N = 800;
else if (n <= 20)
N = 8000;
else N = 38000;
int ans1 = 9999 , ans2 = 0 , rest , now;
while(N--)
{
// 剩余的运动员
rest = n;
// 初始化战斗力
for(int i = 1 ; i <= n ; i++)
{
player[i].a = rand() % 1075943;
player[i].b = i;
}
player[firstPlayer].a = 11000000;
player[secondPlayer].a = 10999999;
// 统计轮次
now = 1;
// 模拟比赛
while(rest > 1)
{
for(int i = 1 ; i <= rest / 2 ; i++)
{
if(player[i].a < player[rest + 1 - i].a)
player[i] = player[rest + 1 - i];
// 统计firstPlayer和secondPlayer相遇轮次的最大值和最小值
if(player[i].b == firstPlayer && player[rest + 1 - i].b == secondPlayer)
ans1 = min(ans1 , now) , ans2 = max(ans2 , now);
}
now++;
rest = (rest + 1) / 2;
sort(player + 1 , player + rest + 1);
}
}
vector<int> ans = {ans1 , ans2};
return ans;
}
};
python3 解法, 执行用时: 52 ms, 内存消耗: 16.2 MB, 提交时间: 2023-10-25 23:43:49
class Solution:
def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:
@cache
def dp(n: int, f: int, s: int) -> (int, int):
if f + s == n + 1:
return (1, 1)
# F(n,f,s)=F(n,n+1-s,n+1-f)
if f + s > n + 1:
return dp(n, n + 1 - s, n + 1 - f)
earliest, latest = float("inf"), float("-inf")
n_half = (n + 1) // 2
if s <= n_half:
# s 在左侧或者中间
for i in range(f):
for j in range(s - f):
x, y = dp(n_half, i + 1, i + j + 2)
earliest = min(earliest, x)
latest = max(latest, y)
else:
# s 在右侧
# s'
s_prime = n + 1 - s
mid = (n - 2 * s_prime + 1) // 2
for i in range(f):
for j in range(s_prime - f):
x, y = dp(n_half, i + 1, i + j + mid + 2)
earliest = min(earliest, x)
latest = max(latest, y)
return (earliest + 1, latest + 1)
# F(n,f,s) = F(n,s,f)
if firstPlayer > secondPlayer:
firstPlayer, secondPlayer = secondPlayer, firstPlayer
earliest, latest = dp(n, firstPlayer, secondPlayer)
dp.cache_clear()
return [earliest, latest]
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.6 MB, 提交时间: 2023-10-25 23:43:28
class Solution {
private:
int F[30][30][30], G[30][30][30];
public:
pair<int, int> dp(int n, int f, int s) {
if (F[n][f][s]) {
return {F[n][f][s], G[n][f][s]};
}
if (f + s == n + 1) {
return {1, 1};
}
// F(n,f,s)=F(n,n+1-s,n+1-f)
if (f + s > n + 1) {
tie(F[n][f][s], G[n][f][s]) = dp(n, n + 1 - s, n + 1 - f);
return {F[n][f][s], G[n][f][s]};
}
int earlist = INT_MAX, latest = INT_MIN;
int n_half = (n + 1) / 2;
if (s <= n_half) {
// 在左侧或者中间
for (int i = 0; i < f; ++i) {
for (int j = 0; j < s - f; ++j) {
auto [x, y] = dp(n_half, i + 1, i + j + 2);
earlist = min(earlist, x);
latest = max(latest, y);
}
}
}
else {
// s 在右侧
// s'
int s_prime = n + 1 - s;
int mid = (n - 2 * s_prime + 1) / 2;
for (int i = 0; i < f; ++i) {
for (int j = 0; j < s_prime - f; ++j) {
auto [x, y] = dp(n_half, i + 1, i + j + mid + 2);
earlist = min(earlist, x);
latest = max(latest, y);
}
}
}
return {F[n][f][s] = earlist + 1, G[n][f][s] = latest + 1};
}
vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
memset(F, 0, sizeof(F));
memset(G, 0, sizeof(G));
// F(n,f,s) = F(n,s,f)
if (firstPlayer > secondPlayer) {
swap(firstPlayer, secondPlayer);
}
auto [earlist, latest] = dp(n, firstPlayer, secondPlayer);
return {earlist, latest};
}
};