#13 Separation

製作者:QCFium

難易度
3

解説


### 2020/02/03 20:14 テストデータに深刻な間違いが発生していましたため、修正しました。本当に申し訳ございません ### 2020/02/03 20:25 問題文が一部消失していたため修正しました。重ねてお詫び申し上げます。 ## 問題 長さ$N$の数列$A$が与えられます。 この数列からいくつかの数を選びます。但し選んだ数は全て互いに$K$以上離れてなければなりません。 最大でいくつの数を選べるかを出力してください。 ## 入力 $N \hspace{8pt} K$ $A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots \hspace{5pt} A_N$ ## 制約 $1 \le N \le 10^5$ $1 \le A_i \le 10^9(1 \le i \le N)$ $1 \le K \le 10^9$ ## 例 ### 入力例1 ``` 6 3 2 11 6 4 10 2 ``` ### 出力例1 ``` 3 ``` 例えば2, 6及び11を選ぶと、選んだ数字は互いに3以上離れていて条件を満たします。 互いに3以上離れている4個以上の数を選ぶことはできません。 ### 入力例2 ``` 5 1 0 10 20 30 40 ``` ### 出力例2 ``` 5 ``` 全部選んでも全て互いに1以上離れているのでOKです。 ### 入力例3 ``` 5 100 0 10 20 30 40 ``` ### 出力例3 ``` 1 ``` 選んだ数字は互いに100以上離れていないとダメですが、一つ選ぶだけなら大丈夫です。 ### 入力例4 ``` 15 4 20 4 3 7 25 14 27 12 10 1 8 16 17 5 14 ``` ### 出力例4 ``` 6 ```
提出