解説:#13 Separation

## 解説 例えば以下のような貪欲法は正しいです - 小さい要素からみていって、差が$K$未満の直近に取った要素がなければ取る 直感的に分かるかもしれませんが - 小さい要素から取るかどうか決めるときに最後に取った要素の情報のみが以降の要素の取り方の可能性に影響する - 最後に取った要素が小さいほど可能性が広がる ことを考えると正しいことが分かります。 元の$A$は小さい順に並んでいるとは限らないので昇順にソートをする必要があります。 実装例は以下の通りです。 ``` #include <bits/stdc++.h> int ri() { int n; scanf("%d", &n); return n; } int main() { int n = ri(), k = ri(); int a[n]; for (auto &i : a) i = ri(); std::sort(a, a + n); int last = -k; int res = 0; for (auto i : a) if (last <= i - k) { res++; last = i; } printf("%d\n", res); return 0; } ```