Fence Repair問題

POJ/蟻本から

3253 -- Fence Repair

蟻本の解説がすごく面白かった。

板を切ることを二分木の枝分かれと考えて、最終的に切られた板一片にかかったコストは板の長さX二分木における深さ。

そう考えると、長さが短い板ほど深くするのが正しいことがわかる。のでまずは一番短い板二片が最後に切られる。次に、その二片の元になった板と、それ以外のすべての板を合わせた集合の中で最も短い二片を・・・となって再帰。

最小のものを取り続けるのでheapがいいんじゃないか、ということでとりあえず書いてみた：

import heapq

def solve(xs):
    ans = 0
    heapq.heapify(xs)
    while len(xs) > 1:
        x = heapq.heappop(xs) + heapq.heappop(xs)
        ans += x
        heapq.heappush(xs, x)
    return ans

heapifyがO(n)で一回、heappopはO(1)（訂正：O(logn)だ）、heappushがO(logn)でどちらもO(n)回呼ばれるのでO(nlogn)なはず。