[백준] 슈퍼컴퓨터 19594 python 풀이

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

핵심

• 프로그램 작업순서 어떻게 배열할 것인지?
  • 끝나는 순서대로
    ⇒ 유사문제 : 회의실 배정
    ⇒ 왜 먼저끝나는 순서인지? 추후 정리필요
    ⇒ 2차원 배열필요한지 아닌지? 추후 정리필요
    
• 최대지각도 계산을 어떻게 효율화 할것인가
  • i번째를 최우선 처리 대상으로 할때 1~i-1, i~N까지 다시 계산하면 빅오 N^2 ⇒ 이때 N은 10만이므로 시간초과
  • 반복되는 최대지각도 계산을 피해야 ⇒ 어떻게 처리? 미리계산 추후 정리필요

"""
Title : 슈퍼컴퓨터
Link : https://www.acmicpc.net/problem/19594
"""
import sys
input = sys.stdin.readline

def solve(n, hours, deadlines):
    dh_list = [(i, j) for i, j in zip(deadlines, hours)]
    dh_list.sort(key=lambda x:x[0])
    s = 0
    late_list = []
    for d, h in dh_list:
        s += h
        late_list.append(max(0, s-d))

    i_max_late_list = []
    temp_max_late = 0
    for l in late_list:
        temp_max_late = max(l, temp_max_late)
        i_max_late_list.append(temp_max_late)

    answer = max(i_max_late_list[-1] - (dh_list[0][1]-1), 0)
    for i in range(1, n):
        tmp = max(i_max_late_list[i-1], max(i_max_late_list[-1] - (dh_list[i][1]-1), 0))
        answer = min(answer, tmp)

    return answer

t = int(input())
for _ in range(t):
    n = int(input())
    h = list(map(int, input().split()))
    d = list(map(int, input().split()))
    print(solve(n, h, d))