[Python] 백준 2513: 통학버스

https://www.acmicpc.net/problem/2513

2513번: 통학버스

1. 학교를 기준으로 왼쪽 오른쪽을 나누어준다. (어차피 학교로 다시 돌아오면 현재 버스 인원이 0명이 되기 때문)

2. 최대힙을 이용하여 거리가 먼순으로 버스에 태운다. (가까운 곳을 우선으로 하면 1 번가 야할 먼 곳을 2번 갈경우도 생기기때문)

3. 현재 버스 인원 + 다음에 가야 할 아파트 인원이 최대를 넘을 경우 학교에 내려다 주고 다시 간다.

from heapq import heappush, heappop

n, k, s = map(int, input().split())
info = [tuple(map(int, input().split())) for _ in range(n)]
lt, rt = [], []
ans = 0

def calc(v):
    global ans
    pNum = 0
    tmp = 0
    while v:
        dis, cnt = heappop(v)
        tmp = max(-dis, tmp)
        if pNum + cnt > k:
            ans += tmp * 2
            heappush(v, (dis, cnt-(k-pNum)))
            pNum = 0
            tmp = 0
        else:
            pNum += cnt

    if tmp:
        ans += tmp * 2
        tmp, pNum = 0, 0

for x in info:
    if x[0] < s:
        heappush(lt, (x[0]-s, x[1]))
    if x[0] > s:
        heappush(rt, (s-x[0], x[1]))

calc(lt)
calc(rt)
print(ans)