36辆车,6条跑道,无计时器,最少几次比赛可以选出前三

时间:2022-06-07 21:38:50

啦啦啦。这是一道面试题目。本来把别人的思路抄一遍,然后转载了。


不过自己还是写成原创了。做贼心虚的多写一点吧。

6条跑道,肯定要首先跑一次
那么自然6条跑道 6次跑完 假设ABCDEF


这样的话A1,A2,A3,B1,B2,B3...F1,F2,F3
18个人


我一开始想他们比较3次得到9个




但是显然可以优化
如下


让A1,B1,C1,D1,E1,F1比赛,设这次比赛代号2


得到他们前三名,假设A1,B1,C1
后三名D1,E1,F1想想他们小组第一都进不了3强,所以那三组直接走人
那么剩下A1,B1,C1,A2,B2,C2,A3,B3,C3
而代号2比赛得到第一名肯定也是36个第一名。因为他比赛2拿到第一了嘛
找到亚军,季军范围,显然下面排列中如果已经确定2个比他牛逼,他最好也是第四,所以淘汰
A2,A3,B1,B2,B3,C1,C2,C3


B1>B2>B3
B1>C1>C2>C3


A2 A3 B1 B2 C1
5个比赛 跑道还剩一个,那么。。。详见后记。
最终得到前三名8个比赛




后记:


空缺意味着可以补录,如果37辆车,6个跑道,其实也可以8次跑完( •̀ ω •́ )
不过面试题目没有这么虐待的,哈哈

36辆车,6条跑道,无计时器,最少几次比赛可以选出前三