Codeforces 263 DIV2 C Appleman and Toastman - いろんなことで四苦Hack（仮）

続き。

内定式で、ブログが途切れてしまったけど、やります。途切れたなら、またやり直せばいいじゃない！！！

問題概要

最初に N 個の数字とスコア 0 が与えられる。それを要素数が 0 にならないように、 2 分割していって、2 分割にした数の和をスコアに加算していく。分けた後の要素の数が 1 になったら、その数字のグループは、削除され、全てのグループの要素が 1 になるまで、その操作を繰り返す。

考えたこと

2 分割したとき、最大の数は、数字の数が 1 じゃないリストの方に入ってる方がいいに決まっている。後で、大きい数が何回も足されるので。ここで、貪欲っぽい考えを使った。

じゃあ、単純に、ソートして、最初とそれ以降を足してを繰り返せばええやんということになる。

""" でかい数を後に残した方がいいに決まってる """
n = int(input())
v = [int(i) for i in input().split()]
v.sort()

ans = sum(v)

for i in range(n-1):
    ans += v[i]
    ans += sum(v[i+1:])
print(ans)

こんな感じになる。 $O(N^{2})$ で抑えられるくらいの計算量になる。多分、正確には違う。

計算量を落とすために、priority queue を使った。

from heapq import heappush, heappop

""" でかい数を後に残した方がいいに決まってる """
n = int(input())
v = [int(i) for i in input().split()]
ans = sum(v)
s = ans
q = []
for i in range(n):
    heappush(q, v[i])
v = None

while len(q) > 1:
    t = heappop(q)
    s -= t
    ans += t
    ans += s

print(ans)

pythonのheapqのモジュールは小さい方が先に出てくる。なので、そのまま使いつつ、最初の合計から引いたのを足していく。s で、最後のグループが、加算されるようにするため、q は、サイズが 1 より大きい場合で、ループをかける。計算量は減ったみたいで、通った。ﾔｯﾀｰ。

いい勉強になった。