【广度优先搜索】【分类讨论】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]解释一种能够产生最早回合数的情景是回合 11, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11回合 22, 3, 4, 5, 6, 11回合 32, 3, 4一种能够产生最晚回合数的情景是回合 11, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11回合 21, 2, 3, 4, 5, 6回合 31, 2, 4回合 42, 4示例 2输入n 5, firstPlayer 1, secondPlayer 5输出[1,1]解释两名最佳运动员 1 和 5 将会在回合 1 进行比拼。不存在使他们在其他回合进行比拼的可能。提示2 n 281 firstPlayer secondPlayer n广度优先搜索每轮的对号左边第i个和右边第i个组成第i对i∈ \in∈[0,(n1)/2]。对号相同必定只保留一人。注意最后一对可能只有一人轮空。性质一交换1号二号队员的位置结果不边。证明在一二号相遇前两队的结果一样保留一二号。等相遇的时候就结束了。性质二任何时刻将整个队伍倒置左边第i变成右边第i位结果不变。倒置后相同的操作结果也是倒置的故不影响一二号相遇。性质三不能只转置一号或二号。如1 , ⋆ ⋆ × × × 2 , ⋆ × × ⋆ × 1 ,\star\star\times \times \times 2,\star\times \times \star\times1,⋆⋆×××2,⋆××⋆×第一种情况最快3回合相遇第二种情况最快第二回合相遇。性质四队伍长度变化: n (n1)/2。用广度优先搜索解决不需要考虑重复状态因为比赛造成队伍长度都会变短。状态一二号队员在当前队伍的编号从左到右编号为[0,n)。计算两个队员的对号小的为i1,大的i2。枚举[0,i1)有i个队员保留(i1,i2)有i个队员保留。只需要考虑两种情况a一二号都在左侧右侧。b一二号不在同一册。代码核心代码classSolution{public:vectorintearliestAndLatest(intn,intfirstPlayer,intsecondPlayer){setpairint,intpre{{firstPlayer-1,secondPlayer-1}};vectorintvRet{0,0};for(intstep1;pre.size();step){setpairint,intdp;intnNewn-n/2;for(auto[fir,sec]:pre){boolbDiff(firnNew)^(secnNew);//是否一个在左边一个在右边#defineNO(a)(min(a,n-1-a))constinti1min(NO(fir),NO(sec));constinti2max(NO(fir),NO(sec));if(i1i2){if(0vRet[0]){vRet[0]step;}vRet[1]step;continue;}constintmidi2-i1-1;for(inti0;ii1;i){//枚举 fir 左边队员 赢的次数for(intj0;jmid;j){// 枚举 fir和 sec的竞争对手 之间队员赢的数量if(bDiff){dp.emplace(nNew-i-1,j(i1-i));}else{dp.emplace(i,i1j);}}}}pre.swap(dp);swap(n,nNew);}returnvRet;}};测试用例templateclassT,classT2voidAssert(constTt1,constT2t2){assert(t1t2);}templateclassTvoidAssert(constvectorTv1,constvectorTv2){if(v1.size()!v2.size()){assert(false);return;}for(inti0;iv1.size();i){Assert(v1[i],v2[i]);}}intmain(){intn11,firstPlayer2,secondPlayer4;{n5,firstPlayer1,secondPlayer4;autoresSolution().earliestAndLatest(n,firstPlayer,secondPlayer);Assert({2,2},res);}{n11,firstPlayer2,secondPlayer4;autoresSolution().earliestAndLatest(n,firstPlayer,secondPlayer);Assert({3,4},res);}{n5,firstPlayer1,secondPlayer5;autoresSolution().earliestAndLatest(n,firstPlayer,secondPlayer);Assert({1,1},res);}{n27,firstPlayer12,secondPlayer13;autoresSolution().earliestAndLatest(n,firstPlayer,secondPlayer);Assert({2,5},res);}}扩展阅读我想对大家说的话亲士工具箱支持AutoCad2013及以上工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作活到老学到老。明朝中后期大约50%的进士能当上堂官(副部及更高)能当上堂官的举人只有十余人。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。视频课程先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。https://edu.csdn.net/course/detail/38771如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程https://edu.csdn.net/lecturer/6176测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。