import sys
import heapq
W, n = map(int, sys.stdin.readline().split())
jw = []
for _ in range(n):
weight, price = map(int, sys.stdin.readline().split())
heapq.heappush(jw, [-price, weight])
result = 0
ww = W
while jw:
p, w = heapq.heappop(jw)
if ww == 0 :
break
elif ww - w <= 0:
tmp = ww
else:
tmp = w
result += tmp*(-p)
ww -= tmp
print(result)
처음에는 그냥 리스트에 받아 정렬했는데(sort함수 사용) 시간초과가 떴다.
제약 조건이
- 1 ≤ N ≤ 10^6인 정수
- 1 ≤ W ≤ 10^4인 정수
- 1 ≤ Mi, Pi ≤ 10^4인 정수
이렇게 되다보니 다 받아서 정렬하지 말고 힙을 사용해야한다.
파이썬 heapq는 디폴트가 최소힙이므로, 가격 최대 순으로 정렬하려면 price에 마이너스를 붙여서 정렬해야한다.
가져갈 수 있는 무게가 0이 될때까지 힙에서 하나씩 pop해서 계산한다.
