クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「Fence Repair（PKU 3253）」(p.75)

Pythonで理解する蟻本（プログラミングコンテストチャレンジブック）

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「Fence Repair（PKU 3253）」(p.75)
のコードをPythonで書き直したものとなっています。

入力

N\\L_1\,…\,L_N

入力例



3
8 5 8

解答

# 順位キュー（優先度付きキュー）をインポートする
import heapq

# 入力
N = int(input())
L = list(map(int,input().split()))

ans = 0

# 順位キュー（優先度付きキュー）を用意
que = []
for i in range(N):
    heapq.heappush(que, L[i])

# 坂が1本になるまで適用
while len(que) > 1:
    # 一番短い板, 次に短い板を取り出す
    l1 = heapq.heappop(que)
    l2 = heapq.heappop(que)
    
    # それらを併合
    ans += l1 + l2
    heapq.heappush(que, l1 + l2)

print(ans)