Sangmun

백준 17976번 Thread knots 본문

알고리즘/백준

백준 17976번 Thread knots

상상2 2023. 5. 13. 00:17

17976번: Thread Knots (acmicpc.net)

 

17976번: Thread Knots

Your program is to read from standard input. The input starts with a line containing one integer, n (2 ≤ n ≤ 100,000), where n is the number of threads. In the following n lines, the i-th line contains two integers xi (0 ≤ xi ≤ 109) and li (1 ≤

www.acmicpc.net

 

* 이분 탐색으로 풀이하는 문제

import sys
input = sys.stdin.readline
n = int(input())

lines = []
for _ in range(n):
    a,b = map(int,input().split())
    lines.append((a,b))

lines.sort()

def search(x):

    before = lines[0][0]

    for each in lines[1:]:

        now = each[0]
        if now - before < x:
            tmp = before + x

            if each[0] <= tmp <= each[0] + each[1]:
                before = tmp
            else:
                return False
        else:
            before = now

    return True

start = 0
end = 2000000000

while start <= end:

    mid = (start + end) // 2
    result = search(mid)

    # 이분탐색으로 문제 풀이
    if result:
        start = mid + 1
    else:
        end = mid - 1

if result: print(mid)
else: print(mid-1)

'알고리즘 > 백준' 카테고리의 다른 글

백준 1495번 기타리스트  (0) 2023.02.06
백준 7490번 0 만들기  (0) 2023.02.04
백준 1449번 수리공  (0) 2023.02.03
백준 1049번 기타줄  (0) 2023.02.03
백준 11057 오르막 수  (0) 2022.12.22
'알고리즘/백준' Related Articles more
Comments