https://www.acmicpc.net/problem/1715
initial
a very simple min heap question. Just one edge case is that when n==1, we need at least 2 values in our min heap. So since there cant be a valid answer, return 0.
reivisted june 11th 24
yep straightforward
solution
import heapq
import math
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
n=int(input())
heap=[]
heapq.heapify(heap)
ans=0
for _ in range(n):
heapq.heappush(heap, int(input()))
if n==1:
print(0)
exit()
while len(heap)>1:
a=heapq.heappop(heap)
b=heapq.heappop(heap)
ans += a+b
heapq.heappush(heap,a+b)
print(ans)complexity
was it n log n for heap operations?
no so firstly heapify is n, push is log n but since we are pushhing n times, it is n log n. So the dominant time is n log n
space is n
