12005번: Diamond Collector (Bronze)

https://www.acmicpc.net/problem/12005


$O(n\lg n)$

정렬한 다음, 차가 k이하가 되는 최대 구간 크기를 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, k, r, d[10000], s;
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", d + i);
    sort(d, d + n);
    for (int i = 0; i < n; i++) {
        if (d[i] - d[s]>k) s++;
        r = max(r, i - s + 1);
    }
    printf("%d", r);
    return 0;
}