- 时间：2019-07-08
- 题目链接：无
- tag：
dAc
有25匹马，速度都不同，但每匹马的速度都是定值。现在只有5条赛道，无法计时，即每赛一场最多只能知道5匹马的相对快慢。
问最少赛几场可以找出25匹马中速度最快的前3名？
七次。
由于每一匹马我们都需要比赛才行，因此至少先比赛 25 / 5 = 5 次， 然后我们可以选择出来每一组的第一名，也就是一共5匹马，再进行一次比赛。这个时候跑第一名的一定是总体第一名。
我们来总结一下，这个时候我们已经决出了第一名，并且比赛了6次。
让我们来分析一下， 假如第六场比赛从第一名到第五名我们依次给其在第一场比赛的场次进行编队为A B C D E。
那么D E所在的一共 5 + 5 = 10 匹马是没有比赛的必要的， 不可能是前三。
C中的只有第一名可能是前三，其他四个我们可以直接舍弃。
B中有可能前三的只有一二名。
A中的二三名也可能是前三。
那么我们只需要把有可能成为前三的 A 中的 2 个， B 中的一个， 以及 C 中 一个 比一下就好了。五个刚好需要一次。
因此一共需要七次。
我们从分治的角度考虑一下， 也就是说怎么将其抽象为一般问题，就是转化为程序。
将原问题表示为f， 那么f(25, 5, 3) 表示25匹马，5个跑道，决出前三。
那么原问题可以转化为：
f(25, 5, 3) = 25 / 5 + f(5,5,1) + f(5,5,2)
那么如果换成10匹马：
f(10, 5, 3) = 10 / 5 + f(5,5,1) + f(4,5,2)
更为精确的代码我就不写了，大家可以自己思考一下。
暂无