n****a
发帖数: 174 | 1 if there were 15 horses, and if you could race 3 at a time. Whats the
minimum number of races that is required to determine the top three horses.
15匹马 3条赛道 没有秒表 问最少次数找出速度最快的前三匹，follow up如果是n匹找
前3匹
谢谢！ |
h****t
发帖数: 69 | 2 We can borrow some of the ideas from the median of median algorithm.
First divide the 15 horses into 5 groups of 3 and race them (Race 1 - 5).
Pick winners of Race 1 - 3 and race them (Race 6). Get the winner of Race 6
to race against the winners of Race 4 - 5 (Race 7). The winner is the
fastest horse.
Now get the second-placed horse of Race 6, 7 and the second-placed horse
behind the fastest horse in Race 1 - 5 (Race 8). The winner is the second-
fastest horse.
Get the two remaining horses of Race 8 and add in the third-placed horse
behind the second-fastest horse in the earlier race(Race 9). The winner is
the third fastest horse.
Total race: 9 |
m*****k
发帖数: 731 | 3 Get the two remaining horses of Race 8 and add in the third-placed horse
behind the second-fastest horse in the earlier race(Race 9).
this only works when the 2nd fastest is not in race 6 and 7. |
h****t
发帖数: 69 | 4 Oh, that's right, I made a mistake in the last race.
Only take the second-placed horse from Race 8. If say the second-placed
horse from Race 6 is the fastest in Race 8, then take the third-placed horse
from Race 6, and the second-placed horse behind it in Race 1-5.
【在 m*****k 的大作中提到】
: Get the two remaining horses of Race 8 and add in the third-placed horse
: behind the second-fastest horse in the earlier race(Race 9).
: this only works when the 2nd fastest is not in race 6 and 7.
|
D*******7
发帖数: 61 | 5 what about the top 3 in one group?
horse
【在 h****t 的大作中提到】
: Oh, that's right, I made a mistake in the last race.
: Only take the second-placed horse from Race 8. If say the second-placed
: horse from Race 6 is the fastest in Race 8, then take the third-placed horse
: from Race 6, and the second-placed horse behind it in Race 1-5.
|
z***y
发帖数: 73 | 6 merge sort吧
5 + 2 + 1 + 1 |
m*****k
发帖数: 731 | 7 exactly.
【在 z***y 的大作中提到】
: merge sort吧
: 5 + 2 + 1 + 1
|
h****t
发帖数: 69 | 8 说merge sort的明显没读清楚题目：没有秒表 |
h*********2
发帖数: 444 | 9 经典题了啊。不过我见过的是25匹马一次比5匹的，本质没区别。2楼正解。 |
z***y
发帖数: 73 | 10 有秒表还需要问几轮？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
再说一遍就是merge sort的思想。
【在 h****t 的大作中提到】
: 说merge sort的明显没读清楚题目：没有秒表
|
