赛马问题

[hushicai]

问题

25匹马，5个跑道，每次只能跑5匹，用最少的次数选出最快的前3匹?

解答

将所有马分成5组，ABCDE。

每组分别先比，决出各组名次，共5次。

第1名肯定从这5个第1名中出来，比一次即可得出第1名，1次。

A1,B1,C1,D1,E1

假设A1最快，E1最慢。

那么第2，3名，则有可能是B1，C1，排除掉D1，E1。

B1不一定就是第2名，它还需要跟A组内的其他马匹pk一下。

同样，C1也不一定就是第3名，它还需要跟A组或者B组其他马匹pk一下。

A组中A2，A3有可能冲击。

B组中B1，B2有可能冲击。

最终拎出以下几匹马：

A2,A3,B1,B2,C1

比一次就可得到2,3名。

最少比7次可决出前3名。

[hushicai]

知乎上还有人用二叉堆、有向边来解决这个问题。