[ BOJ ][JAVA][17976] Thread Knots

www.acmicpc.net/problem/17976

17976번: Thread Knots

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	776	271	172	29.503%

문제

There are n threads on the x-axis. The length of the i-th thread, say Ti, is denoted by li and the location of its starting point by xi, both being integers. We want to make a knot in each thread. The location of the knot must also be an integer. The knot can be made at any point in the thread and it is assumed that the length of the thread is not reduced by the knot. You can assume that no thread is totally contained by another, which means that there are no two thread Ti and Tj (i ≠ j) such that xj ≤ xi and xi+li ≤ xj+lj.

We want to determine the location of the knot for each thread in order to make the distance between the closest two neighboring knots as big as possible.

For example, the figures below show the locations of the knots for six threads. The location of a knot is denoted by a point. All the threads actually lie on the x-axis, however, they are drawn separately to distinguish each other. In Figure I.1, the distance between the closest two knots is 20. However, if we make the knot for T2 at different location as shown in Figure I.2, the distance between the closest two knots becomes 25, which is what this problem requests.

Figure I.1: An example of knots for 6 threads.

Figure I.2: Another example with different location of knot for T2.

Given information about the n threads, write a program that calculates the maximum distance between two closest 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 ≤ li ≤ 109), where xi and li denote the location of the starting point and the length of the i-th thread, respectively, You can assume that no thread is totally contained by another, which means that there are no two threads Ti and Tj (i ≠ j) such that xj ≤ xi and xi+li ≤ xj+lj.

출력

Your program is to write to standard output. Print exactly one line. The line should contain an integer which is the maximum distance between two closest knots.

예제 입력 1

6
0 67
127 36
110 23
50 51
100 12
158 17

예제 출력 1

25

예제 입력 2

6
0 40
10 55
45 28
90 40
83 30
120 30

예제 출력 2

30

예제 입력 3

3
0 20
40 10
100 20

예제 출력 3

50

코드

/*
    Greedy + binary search
    자료형 타입이 int면 maxLen이 넘어가서 잘못된 연산이 수행된다.
    mid가 잘못 계산되어 lo가 계속해서 올라가는 것이 반복되면, 결국 lo도 MAX를 넘어서며 오버플로우.
    때문에 lor가 hi보다 커지는 것이 아니라 오히려 음수로 가게 되어 무한 반복 -> 시간초과
    + 이와 같은 undefined behavior는 전혀 예상하지 못한 방향으로 어떤 행동으로도 무한루프에 빠지는 것이 충분히 가능하다.
*/
import java.io.*;
import java.util.*;

public class p17976 {
    static class Pair implements Comparable<Pair>{
        int a, b;
        public Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }

        public int compareTo(Pair p) {
            return a - p.a;
        }
    }
    static int n;
    static Pair[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        arr = new Pair[n];
        long maxLen = 0;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            arr[i] = new Pair(a, a + b);
            maxLen = Math.max(maxLen, a + b);
        }
        Arrays.sort(arr);

        // 이분탐색 진행
        // left와 right 포인터의 값이 불변한 곳을 정확히 찾는게, 이분탐색에서 실수하지 않는 방법이다!
        // 나올 수 있는 최소 차이 : 0, 최대 차이 : 맨 오른쪽
        long start = 0;
        long end = maxLen;
        long answer = 0;
        while (start <= end) {  // - 최적화 문제
            long mid = (start + end) / 2;
            // 두 선분의 차이를 mid로 할 수 있는 선분위의 두 점이 존재하는가 ? - 결정 문제
            if (promising(mid)) {
                answer = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        // 출발점을 기준 정렬
        System.out.println(answer);

    }

    static boolean promising(long val) {
        // 맨처음 위치는 실의 출발점
        long now = arr[0].a;
        for (int i = 1; i < n; i++) {
            // val와 출발점을 더한 것이 다음 실의 범위를 벗어난다면 false
            if (now + val > arr[i].b) return false;
            else {
                now = Math.max(arr[i].a, now + val);
            }
        }
        return true;
    }
}