LUNCHBOX

도시락데우기 문제입니다.
https://algospot.com/judge/problem/read/LUNCHBOX
지문이 길기 때문에 링크로 대신하겠습니다.

하지만 영어지문이기 때문에 요약해서 적어보겠습니다.

n개의 냉동식품이 있습니다. 냉동식품마다 먹는데 걸리는 시간(E) 과 전자레인지에 조리하는 시간(M)이 가지각색입니다. 하지만 PX에는 전자레인지가 하나 밖에 없어서 한번에 하나의 냉동식품밖에 데울 수 없습니다. 각 사람은 자기음식을 다데우는대로 다른사람들을 기다리지 않고 곧장 먹기 시작합니다.
PX병은 PX이용시간을 최소화하는 계획을 짜고 싶어합니다. 어느 순서로 냉동식품을 데워야 가장 빨리 PX이용시간을 마칠 수 있을지 결정하는 프로그램을 작성하세요.

위와 같은 순서를 정해야하는 문제는 어떤 변수(E or M)를 기준으로 순서를 정할 지를 생각해봐야합니다. 즉, 어떤 변수가 최종 시간을 결정하는지를 파악하면 됩니다.

간단하게 직관적으로 모든 냉동식품을 전자레인지로 돌리는 시간은 항상 같다는 걸 알 수 있습니다. 그렇다면 먹는 것이 최종 시간을 결정함을 알 수 있습니다. 한 종류의 냉동식품만 먹는 시간이 다른 극단적인 예를들어 보겠습니다.
(M, E) : [(2, 2), (2, 2), (2, 4), (2, 2)]
가장 오래 걸릴 경우는 먹는데 4 가 걸리는 식품을 마지막에 먹는 경우입니다.
(2 + 2 + 2 + 2) + 4
해당 식품을 조금식 앞으로 옮겨보면 최종시간이 짧아지는 것을 알 수 있습니다.
즉, 저희는 먹는 시간을 내림차순으로 정렬하는 순서를 가지게 되면 가장 최적인 시간을 얻을 수 있습니다.

정당성 증명

이전과 동일하게 저희 방식을 따르지 않는 최적해를 가정해봅시다.
예를들면 먹는데 가장 오래걸리는 A식품을 맨 처음 먹지않았지만 최적해를 얻은 경우입니다.
그렇다면 그 상태에서 A식품의 순서를 맨앞으로 당긴다면 결과가 어떻게 변화할 가요?
짧아지거나 혹은 변화가 없을 겁니다. 여기까지만 해봐도 저희 방식이 최적해에 포함된다는 것을 알 수 있습니다.

구현

import heapq
def solution(boxs):
    boxs = [(-e, m) for m, e in boxs]
    heapq.heapify(boxs)
    sum_micro = 0
    ret = 0
    while boxs:
        eat, micro = heapq.heappop(boxs)
        sum_micro += micro
        ret = max(ret, sum_micro - eat)
    return ret

C = int(input())
for _ in range(C):
    input()
    micro_time = list(map(int, input().split()))
    eat_time = list(map(int, input().split()))
    boxs = list(zip(micro_time, eat_time))
    print(solution(boxs))