a*******8
发帖数: 2299 | 1 49 辆赛车.
Assume for each one, it travels the track in the same amount of time every
time. Also assume no two finish the track in the same amount of time.
Suppose you have 7 tracks, but no timer. Design races to find the 25-th
fastest with minimal number of races. |
p********7
发帖数: 549 | 2 老题了，
分7组，查linear selection wiki，解法类似 |
n******h
发帖数: 50 | 3 忘记答案了。7组分别赛，然后赛每组的第4名？然后呢…… |
p********7
发帖数: 549 | 4 每组第四比赛，获得median，比如
A1 A2 A3 A4 A5 A6 A7
B1 B2 B3 B4 B5 B6 B7
C1 C2 C3 C4 C5 C6 C7
D1 D2 D3 D4 D5 D6 D7
E1 E2 E3 E4 E5 E6 E7
F1 F2 F3 F4 F5 F6 F7
H1 H2 H3 H4 H5 H6 H7
A4>B4>C4>D4>E4>F4>H4
一定比D4快的就有A1-A4 B1-B4 C1-C4 D1-D3一共15个，一定比他慢的D5-7....一共15个
把其他不确定的18个分3组和D4比较。最差情况是D4比这18都慢，或者都快。如果D4比
这18个都快，
那么就成从18+15个里面找第9大的数，我再考虑下，后面的解法应该不是linear selection
这题还真有难度，我在网上也没找到权威的答案啊，不知道最优办法到底能在最差情况下用多少次解出
答案 |
