※ 引述《Leon (Achilles)》之铭言： : : 这题是考 怎麽找 Median, 你可以用 Quick Sort 的变形去找. : : 你先考虑一下简单的题目: : 要是有 9 cars, and has a run way with 3 laps : How to do it? : : First round: do a run with 3 cars, we need 3 games. : : Second round: We pick the 'median' of the first round, : thus, we will have `median of the median'. : : We call it X. : : Now, we are sure 3 cars are faster than X, 3 cars are slower than X. : 2 cars are unknown. : : Third round will be X and 2 unkonws. : : 用这个 Median of Median 的原理, 你就能解那个 49 cars case. : 我就留给你自己补完了. : : : : : -- :

※ 发信站: 批踢踢实业坊(ptt.cc) : ◆ From: 142.136.127.112 : 推 RockLee:不好意思不是很懂L大的意思 Third round拿X跟2 unkonws比 02/13 15:52 : → RockLee:就可以知道5th吗? 以下123与ABC的情形要如何区分呢? 02/13 15:52 : → RockLee:(game 1) 1 2 9 (game A) 1 2 7 02/13 15:52 : → RockLee:(game 2) 3 4 5 (game B) 3 4 6 02/13 15:52 : → RockLee:(game 3) 6 7 8 (game C) 5 8 9 02/13 15:53 就用你的例子讲解. After Game (1, 2, and 3), we know the median of the first round is car with number 2, 4, 7. Then in the second round, we compare car 2, 4, 7. Assume the result is 4-2-7. car 4 is the fastest in second round. In this case, we know car 2 is the median of the median. Now it's clear that car 2 is slower than 1, and 4, 3 but faster than 9, and 7,8. So in the third round we just need to compare car with number 2 and two unclear 5 and 6. 你懂了吗? --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 142.136.127.112