推荐|【广度优先搜索】【分类讨论】900. 最佳运动员的比拼回合

作者推荐

本文涉及知识点

LeetCode : 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 <= 28
1 <= firstPlayer < secondPlayer <= n

广度优先搜索

每轮的对号：左边第i个和右边第i个组成第i对，i $\in$ [0,(n+1)/2]。对号相同必定只保留一人。注意：最后一对可能只有一人轮空。
性质一：交换1号二号队员的位置结果不边。证明：在一二号相遇前，两队的结果一样：保留一二号。等相遇的时候，就结束了。
性质二：任何时刻，将整个队伍倒置，左边第i变成右边第i位，结果不变。倒置后，相同的操作，结果也是倒置的，故不影响一二号相遇。
性质三：不能只转置一号或二号。如：
$,\star\star\times \times \times 2,\star\times \times \star\times$
第一种情况，最快3回合相遇，第二种情况，最快第二回合相遇。
性质四：队伍长度变化: n = (n+1)/2。

用广度优先搜索解决，不需要考虑重复状态，因为比赛造成队伍长度都会变短。
状态：一二号队员在当前队伍的编号，从左到右编号为[0,n)。
计算两个队员的对号，小的为i1,大的i2。枚举[0,i1)有i个队员保留，(i1,i2)有i个队员保留。
只需要考虑两种情况：
a，一二号都在左侧（右侧）。
b，一二号不在同一册。

代码

核心代码

class Solution {
public:
	vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
		set<pair<int, int>> pre = { {firstPlayer-1, secondPlayer-1 } };
		vector<int> vRet = { 0,0 };
		for (int step = 1; pre.size(); step++)
		{			
			set<pair<int, int>> dp;
			int nNew = n - n / 2;
			for (auto [fir, sec] : pre)
			{				
				bool bDiff = (fir < nNew) ^ (sec < nNew);//是否一个在左边，一个在右边
# define NO(a)  ( min(a,n-1-a))
				const int i1 = min(NO(fir), NO(sec));
				const int i2 = max(NO(fir), NO(sec));
				if (i1 == i2)
				{
					if (0 == vRet[0])
					{
						vRet[0] = step;
					}
					vRet[1] = step;
					continue;
				}
				const int mid = i2 - i1 - 1;
				for (int i = 0; i <= i1; i++)
				{//枚举 fir 左边队员 赢的次数
					for (int j = 0; j <= mid; j++)
					{// 枚举 fir和 sec的竞争对手 之间队员赢的数量	
						if (bDiff)
						{
							dp.emplace(nNew-i-1, j + (i1-i));
						}
						else
						{
							dp.emplace(i, i+1+j);
						}
					}
				}
			}
			pre.swap(dp);
			swap(n,nNew);
		}
		return vRet;
	}
};

测试用例

template<class T, class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{
	int n = 11, firstPlayer = 2, secondPlayer = 4;
	{
		n = 5, firstPlayer = 1, secondPlayer = 4;
		auto res = Solution().earliestAndLatest(n, firstPlayer, secondPlayer);
		Assert({ 2,2 }, res);
	}
	{
		n = 11, firstPlayer = 2, secondPlayer = 4;
		auto res = Solution().earliestAndLatest(n, firstPlayer, secondPlayer);
		Assert({ 3,4 }, res);
	}	
	{
		n = 5, firstPlayer = 1, secondPlayer = 5;
		auto res = Solution().earliestAndLatest(n, firstPlayer, secondPlayer);
		Assert({ 1,1 }, res);
	}
	{
		n = 27, firstPlayer = 12, secondPlayer = 13;
		auto res = Solution().earliestAndLatest(n, firstPlayer, secondPlayer);
		Assert({ 2,5 }, res);
	}
	
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

文章知识点与官方知识档案匹配，可进一步学习相关知识

算法技能树首页概览60496 人正在系统学习中

群中有博文配套源码

QQ群名片