대형 쇼핑몰에서 쇼핑을 마친 N명의 고객들이 계산을 하고 쇼핑몰을 떠나고자 계산대 앞에 줄을 서 있다. 각 고객은 커다란 짐수레(cart)에 물건을 담아 계산대로 간다. 쇼핑몰에는 아래 그림과 같이 K개의 계산대가 병렬로 배치되어 있다. 쇼핑몰 안내원들은 계산대에 온 사람들을 가장 빨리 계산을 마칠 수 있는 계산대로 안내를 한다. 안내원은 각 계산대에서 기다리고 있는 사람들이 계산을 하는데 얼마나 걸리는지 이미 알고 있다.
안내원이 고객을 계산대로 안내할 때 두 계산대에서 기다려야 할 시간이 같을 경우에는 가장 번호가 작은 계산대로 안내를 한다. 즉 3번, 5번 계산대에서 기다릴 시간이 똑같이 15분으로 최소일 경우에는 3번으로 안내를 한다.
계산을 마친 고객은 출구를 통하여 쇼핑몰을 완전히 빠져 나간다. 만일 계산대에서 계산을 마친 고객의 시간이 동일하다면 출구에 가까운 높은 번호 계산대의 고객부터 먼저 빠져나간다. 예를 들어 두 계산대 4번과 10번에서 두 고객이 동시에 계산을 마쳤다면 계산대의 번호가 더 높은 10번 계산대의 고객이 먼저 쇼핑몰을 나간다. 물건을 계산하는 데에는 종류에 관계없이 동일하게 1분이 소요된다. 즉, 물건이 w개 있는 손님이 계산을 마치는 데에는 정확히 w분이 소요된다.
여러분은 계산대로 들어가기 위하여 줄을 서 있는 고객 N명의 정보( 회원번호, 구매한 물건의 수)를 알고 있을 때, 이들이 계산을 하고 쇼핑몰을 빠져나오는 순서를 구해야 한다. 계산대로 들어가고 계산대에서 나오는데 걸리는 시간은 없다고 가정한다.
입력의 첫 줄에는 2개의 정수 N(1 ≤ N ≤ 100,000)과 k(1 ≤ k ≤ 100,000)가 주어진다. 다음 줄부터 N개의 줄에 걸쳐 고객 N명의 정보가 줄 맨 앞의 고객부터 맨 뒤 고객까지 순서대로 주어진다. i번째 줄은 줄의 앞에서 i번째 고객의 회원번호 idi(1 ≤ idi ≤ 1,000,000)와 그가 구입한 물건의 수 wi(1 ≤ wi ≤ 20)로 이루어져 있다. N명의 회원번호는 모두 다르다.
출력
고객 N명의 회원번호를 쇼핑몰을 빠져나가는 순서대로 r1, r2, ..., rN이라 할 때, 1×r1 + 2×r2 + ... + N×rN의 값을 출력한다. 출력값이 int 범위를 넘어갈 수 있음에 유의하라.
손님이 들어올 때 시점으로 빈 계산대 자리를 조건(낮은 계산대 우선)에 따라 배치하면 되므로, 우선순위 큐를 사용할 수 있겠다. 하지만 손님이 나갈 때는 높은 계산대 우선순위로 나가게 되며, 우리는 나가는 순서를 참조하여 정답을 구해야 한다. 따라서 우선순위 큐를 두 개 이용해 볼 수 있겠다.
빈 계산대 우선순위 큐
현재 계산대 우선순위 큐
손님이 들어올 때 우리는 다음 알고리즘에 따라 처리해 볼 수 있다.
만약 빈 계산대 우선순위 큐의 자리가 있다면, 빈 계산대 큐에서 pop하여 가장 높은 순위의 계산대를 할당받는다. 그리고 현재 계산대 우선순위 큐에 손님의 아이디를 삽입한다. 우선도는 (계산이 끝나는 시점, -현재 계산대 인덱스)가 된다(두 우선순위 큐의 계산대 인덱스에 대한 중요도가 반대이기 때문)
그렇지 않다면, 현재 계산대 우선순위 큐를 pop해야 한다. 여기서 주의해야 할 점은, 만약 계산이 끝나는 시점이 동일한 계산대가 둘 이상 존재할 경우 모두 pop해주어야 한다. 이를태면 3번, 5번 계산대가 같은 시점에 계산이 종료될 경우 나가는 순서는 (5, 3)이지만 이후 다음 손님이 배치되는 순서는 (3, 5)순이 된다.
pop할 때마다 정답을 업데이트하고, 빈 계산대 우선순위 큐에 계산대 정보를 업데이트한다.
이후 위와 같이 빈 계산대 우선순위 큐에 현재 손님을 배치하도록 한다. 계산이 끝나는 시점은 (pop된 계산대의 끝나는 시점 + 현재 계산이 끝나는 시점 w)가 됨에 주의하자.
풀이 코드
from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline
N, k = map(int, input().split())
casher_list = list()
empty_casher_list = list(range(k))
heapify(empty_casher_list)
answer = 0
idx, t = 1, 0
for _ in range(N) :
id, w = map(int, input().split())
if len(casher_list) == k :
t = casher_list[0][0]
while casher_list and casher_list[0][0] == t :
_, prev_casher, prev_id = heappop(casher_list)
heappush(empty_casher_list, -prev_casher)
answer += idx*prev_id
idx += 1
heappush(casher_list, (t + w, -heappop(empty_casher_list), id))
while casher_list :
_, _, prev_id = heappop(casher_list)
answer += idx*prev_id
idx += 1
print(answer)
