作者windows2k (KERORO军曹)
站内Prob_Solve
标题Re: [问题] 数值合并
时间Mon Jul 10 10:18:24 2006
※ 引述《march20 ()》之铭言：
: 嗯, 看到这个 case, 给了我一个灵感 (先 po 出来看看)
: Huffman 找值最小的两个来合并,
: 这里似乎要找相邻和最小的两数来合并.
: 比如 10+7, 7+2, 2+4, 4+12, 12+6, 所以先拿 2,4 来合并.
: 然後 update heap 时, 要将影响到的邻居一并 update
: 比如第一轮找到 2+4 为最小,
: 那就把 2+4 pop 出来, 这时影响到的 node 就是 7+2 和 4+12
: 要将这两个值变成 7+6 和 6+12 然後调整 heap.
不知道是否我有误解你的意思
假设这个例子
5 3 4 5
一开始是先拿 3 4 合并
5 7 5
12 5
17
Total cost:36
Optimal Solution:
5 3 4 5
8 4 5
8 9
17
Total cost:34
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.115.156.192
1F：推 march20:you're right, 这也不是 optimal solution 07/10 10:24
2F：推 march20:看来不简单喔 @@ 07/10 10:24
3F：推 march20:btw, 你是怎麽知道有 n lg n 的 solution 的呢? 07/10 10:24
4F：推 march20:感觉上, 这问题是要造出某种 balacne 的 tree 07/10 10:32