/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は旅行会社の添乗員です。今度のバスツアーには N 人の参加者が申し込んでおり、それぞれの参加者には希望する出発時刻があります。
各参加者 i (1 \leq i \leq N) の希望出発時刻は T_i です。旅行会社の方針では、効率的にツアーを運営するために、希望出発時刻が近い参加者たちを同じバスにまとめて出発させます。具体的には、同じバスに乗るどの 2 人の参加者 i, j についても、希望出発時刻の差の絶対値 |T_i - T_j| が K 以下でなければなりません。なお、1 台のバスに乗せられる人数に上限はありません。
高橋君は、すべての参加者をちょうど 1 台ずつバスに振り分けて、必要なバスの台数を最小にしたいと考えています。
すべての参加者をバスに振り分けるために必要な最小のバスの台数を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- 0 \leq T_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数
入力
N K T_1 T_2 \ldots T_N
- 1 行目には、参加者の人数を表す N と、同じバスに乗せられる希望出発時刻の差の絶対値の上限を表す K が、スペース区切りで与えられる。
- 2 行目には、各参加者の希望出発時刻を表す T_1, T_2, \ldots, T_N が、スペース区切りで与えられる。
出力
すべての参加者をバスに振り分けるために必要な最小のバスの台数を 1 行で出力してください。
入力例 1
5 3 1 5 3 9 12
出力例 1
3
入力例 2
8 10 5 100 15 8 95 20 105 12
出力例 2
3
入力例 3
15 5 0 1 2 10 11 12 13 25 30 31 32 33 50 100 101
出力例 3
6
Score : 300 pts
Problem Statement
Takahashi is a tour conductor at a travel agency. For the upcoming bus tour, N participants have signed up, and each participant has a preferred departure time.
The preferred departure time of each participant i (1 \leq i \leq N) is T_i. According to the travel agency's policy, to operate tours efficiently, participants with similar preferred departure times are grouped together on the same bus. Specifically, for any two participants i, j on the same bus, the absolute difference of their preferred departure times |T_i - T_j| must be at most K. There is no upper limit on the number of people that can ride on a single bus.
Takahashi wants to assign every participant to exactly one bus and minimize the number of buses required.
Find the minimum number of buses needed to assign all participants to buses.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- 0 \leq T_i \leq 10^9 (1 \leq i \leq N)
- All inputs are integers
Input
N K T_1 T_2 \ldots T_N
- The first line contains N, the number of participants, and K, the maximum allowed absolute difference in preferred departure times for participants on the same bus, separated by a space.
- The second line contains the preferred departure times T_1, T_2, \ldots, T_N of each participant, separated by spaces.
Output
Print the minimum number of buses needed to assign all participants to buses, on a single line.
Sample Input 1
5 3 1 5 3 9 12
Sample Output 1
3
Sample Input 2
8 10 5 100 15 8 95 20 105 12
Sample Output 2
3
Sample Input 3
15 5 0 1 2 10 11 12 13 25 30 31 32 33 50 100 101
Sample Output 3
6