백준 2230 수 고르기

문제

N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오.

예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M = 3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.

입력

첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다.

출력

첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있다.

제한

• 1 ≤ N ≤ 100,000
• 0 ≤ M ≤ 2,000,000,000
• 0 ≤ |A[i]| ≤ 1,000,000,000

예제 입력 1 복사

3 3
1
5
3

예제 출력 1 복사

4

 

• 풀이

 

Arrays.sort로 정렬을 하지 않는 실수때문에 답이 이상한건지 많이 해멨다..

구간합이 아닌 두개만 고르는 문제라 정렬을해도 두개를 고르는 경우에는 영향이 없으니 정렬을하고

아래 식처럼 두개를 골라야 답을 맞출 수 있다

import java.io.*;
import java.util.*;

class Main {

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();

        int[] arr = new int[n + 1];
        for (int i = 1; i <= n; i++) arr[i] = in.nextInt();

        Arrays.sort(arr);

        int rt = 1;

        int ans = 2000000001;

        for (int i = 1; i < n; i++){
            while (rt < n && arr[rt] - arr[i] < m){
                rt++;
            }

            int diff = arr[rt] - arr[i];
            if (diff >= m) ans = Math.min(diff, ans);
        }

        System.out.println(ans);
    }
}