BOJ)2230 수 고르기

문제: icpc.me/2230

N개의 원소로 이루어진 수열에서 두 수를 뽑았을 때 그 수의 차이가 M보다 크면서 가장 작은 두 수의 차이를 구하는 문제이다.

우리는 정렬을 해준 뒤 투 포인터 i , j 를 설정하여 문제를 해결할 수 있다.

a[i]-a[j]가 m보다 작다면 두 수의 차이가 더 커져야 하므로 i를 증가시키고 m보다 크거나 같다면 j를 증가시키는 방법으로 해결해나가면 된다.

#include <cstdio>
#include <algorithm>
#define INF 1987654321
using namespace std;
int n, m, a[100001], r;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    sort(a, a + n);
    int j = 0;
    r = INF;
    for (int i = 0; i < n&&j < n;) {
        if (a[i] - a[j] >= m) {
            r = min(r, a[i] - a[j]);
            j++;
        }
        else 
            i++;
    }
    printf("%d\n", r);
    return 0;
}