来点补充说明, 因为 step 2 (refine) 不是一个很明显的动作 (在这几个 case 里) ※ 引述《sandwichC (没回应=挂站)》之铭言： : 投影片中的例子 : S 10 7 2 4 12 6 : ---------------------------------------------------------- : R.M. 10 7 6 12 6 (2,4各加一次) : refine 10 7 6 12 6 2+4 是 RM, 因为 2+4 <= 12, 所以 (2+4) 要被 "移" 到 12 前 order 刚好没变. : ---------------------------------------------------------- : R.M. 10 7 6 18 (12,6各加一次) : refine 10 7 6 18 同上 : ---------------------------------------------------------- : R.M. 10 13 18 (7,2,4各加一次) : refine 10 13 18 同上 : ---------------------------------------------------------- : R.M. 23 18 (10,7,2,4各加一次) : refine 18 23 注意罗, 这里不一样! 10+13 之後, 没有任何一个 single entry 大於或等於 23, 所以 23 移到最後. : ---------------------------------------------------------- : R.M. 41 (10,7,2,4,12,6各加一次) : total: 10加了两次 (level = 2) : 7加了三次 (level = 3) : 2加了四次 (level = 4) : 4加了四次 (level = 4) : 12加了两次 (level = 2) : 6加了两次 (level = 2) : 故建出的tree： : | : ----------------- : | | : | ------------- : | | | : | | ----------- : | | | | : ------- | | -------- : | | | | | | : 12 6 10 7 2 4 ^^^^^^^^^ 注意到了吗? 12 6 本来是在 4 之後, 现在跑到最前面来了. 有一件事投影片没讲清楚: "把上面那颗树变成另一颗树, 其中各 leaf 的 depth 与在原树中相同, 但 leaves 的顺序与原数列一样." 至於怎麽变, 这样为什麽会找到最佳解, 就看看之前给的 link 吧 (其实我没真的 go through 过, 但这比 windows2k 兄给的 slides 完整些 :P) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 71.137.27.253 ※ 编辑: march20 来自: 71.137.27.253 (07/18 15:00) ※ 编辑: march20 来自: 71.137.27.253 (07/18 15:01) ※ 编辑: march20 来自: 71.137.27.253 (07/18 15:02) ※ 编辑: march20 来自: 71.137.27.253 (07/18 15:02) ※ 编辑: march20 来自: 71.137.27.253 (07/18 15:03)