문제요약

$N (1 \leq N \leq 100,100)$개의 노래가 주어진다. 각 노래는 재생시간 $D(1 \leq D \leq 1000)$와 다운로드 시간 $V (1 \leq V \leq 1000)$가 주어진다 .

각 노래는 순서대로 들어야 하고, 이전 노래가 다운로드 완료되어야 다음노래를 다운로드 할 수 있다.

이때, 끊김없이 다운로드가 되어있는 노래를 듣기 위해서는, 처음 다운로드를 시작한지 몇 초 후에 노래를 듣기 시작해야하는지 구하시오.

풀이

모든 노래를 들을 수 있는 최소 대기 시간을 $T = t$라 하자. 이 때, $T = x \ (t \leq x)$에 대해 $x$시간 대기 한 후에도 모든 노래를 들을 수 있다. 따라서 단조성이 보장된다. 매개 변수 탐색과 시뮬레이션을 이용하자. 시간복잡도는 $\mathcal O(NlogT)$이다. $T =$ 시작시간으로 가능한 최대시간 $\approx NV$

정답코드

import sys
input = sys.stdin.readline

def check(x):
    now = x
    flg = 1
    for i in range(n):
        now -= song[i][1]
        if now < 0: flg = 0
        now += song[i][0]
    return flg
    
n = int(input())
song = [list(map(int, input().split())) for _ in range(n)]

left = 0
right = int(1e9)

while left + 1 < right:
    mid = (left + right)//2
    if check(mid): right = mid
    else: left = mid

print(right)