🐴无了,人傻了
Pin Young Lv9

请听题:

有64匹🐴,一共8个赛道,需要多少次比赛可以知道当中最快的4匹🐴


最近偶然看帖子看到了这么一个算法问题,我因为一直都是在写业务,对算法这块也没有太研究过,知道的也就只有什么二分查找,二叉树,冒泡排序啥的,所以看到这个题的第一反应就是递归。。。。。。。好吧,我是真滴🥬

好在原文有配图,看起来不费力,我终于是理解到了原理,故我自己记录一下加深理解。

解题思路:

先把64匹🐴分成[A, B, C, D, E, F, G, H]8组,每组8匹

https://qiniu.sukoshi.xyz/attach/2021/04/16/Snipaste_2021-04-16_10-24-40-1.png

每组各跑一次,可以得到每组的第一名🐴👑,然后吧每组的最后四名剔除掉(这很好理解,每组的最后四名肯定不会是最快的四匹马啦)黄色的🐴被淘汰 (比赛8次)

https://qiniu.sukoshi.xyz/attach/2021/04/16/Snipaste_2021-04-16_10-25-58-2.png

把每组的第一名🐴👑一共8匹马再来赛一次,把里面后四名🐴跟它所在的组([E, F, G, H])一起剔除掉(这也很好理解,8个组派出了8个代表🐴👑,最后四名跑不过前四名,那么最快的四匹肯定不会在后四名所在的组里)蓝色的🐴被淘汰 (比赛1次)

https://qiniu.sukoshi.xyz/attach/2021/04/16/Snipaste_2021-04-16_10-26-19-3.png

现在就只剩下A组(A1-A4),B组(B1-B4),C组(C1-C4),D组(D1-D4),现在可以知道A1🐴是总冠军(在小组里跑第一,又在各个小组第一里跑第一)跑的最快,现在就只需要找到剩下的三匹🐴。

我们先看B组,假设B组的🐴都是潜力股,B4这匹🐴还是会被淘汰(A1 > B1,B2,B3,B4 > A2 只取前三),B4被淘汰。

再看C组,根据B组假设规则推类,C3,C4这两匹🐴还是会被淘汰(A1 > B1 > C1,C2,C3,C4 > B2 只取前二),C3,C4被淘汰。

D组D2,D3,D4这三匹🐴会被淘汰(A1 > B1 > C1 > D1,D2,D3,D4 > C2 只取D1),所以D2,D3,D4被淘汰。

由以上整理以后,得到下面结果橙色的🐴被淘汰

https://qiniu.sukoshi.xyz/attach/2021/04/16/Snipaste_2021-04-16_10-27-10-4.png

最后再在剩下的9匹🐴中随机挑出8匹🐴跑一次,拿出前三名🐴。(比赛1次)

用这前三名🐴在跟刚刚剩下的那匹🐴跑一次,拿出前三名🐴。 (比赛1次)

再加上总冠军🐴👑,最快的四匹🐴就出现啦!🎉🎉🎉

最后一共需要8+1+1+1=11次


最后看到原帖评论区有个优化方案,在第三次比赛的时候,把除A2的剩余8匹🐴来比赛,如果A3为第一,那么直接取前两名🐴在加上A1,A2得到最后的四匹🐴,这样可以少比赛一次。总计10

如果不是,则按照上面第四次比赛流程,在比赛一次即可获取最快的四匹🐴。