/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は洗濯物を片付けています。洗濯かごの中には N 枚の靴下があり、i 番目の靴下 (1 \leq i \leq N) には色の濃さを表す整数値 A_i が設定されています。異なる靴下が同じ色の濃さを持つこともあります。
高橋君はこれらの靴下からペアを作りたいと考えています。高橋君は几帳面な性格なので、2枚の靴下をペアにするには、それらの色の濃さの差の絶対値が K 以下である必要があります。すなわち、i 番目の靴下と j 番目の靴下 (i \neq j) をペアにできるのは、|A_i - A_j| \leq K を満たすときに限ります。
1つのペアはちょうど2枚の靴下からなり、各靴下はたかだか1つのペアにしか使用できません。ペアに使われない靴下が残っても構いません。
高橋君が作ることができる靴下のペアの最大個数を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、靴下の枚数を表す整数 N と、ペアとして認める色の濃さの差の上限を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各靴下の色の濃さを表す N 個の整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
高橋君が作ることができる靴下のペアの最大個数を 1 行で出力せよ。
入力例 1
6 2 1 3 5 2 8 7
出力例 1
3
入力例 2
10 3 1 5 9 13 17 2 6 10 14 18
出力例 2
5
入力例 3
15 100 50 200 350 500 120 80 210 340 510 130 75 220 360 490 140
出力例 3
6
Score : 300 pts
Problem Statement
Takahashi is putting away the laundry. There are N socks in the laundry basket, and the i-th sock (1 \leq i \leq N) has an integer value A_i representing its color intensity. Different socks may have the same color intensity.
Takahashi wants to make pairs from these socks. Being a meticulous person, he requires that the absolute difference in color intensity between two socks in a pair is at most K. That is, the i-th sock and the j-th sock (i \neq j) can be paired only if |A_i - A_j| \leq K.
Each pair consists of exactly 2 socks, and each sock can be used in at most one pair. It is fine if some socks are left unpaired.
Find the maximum number of pairs of socks that Takahashi can make.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9
- All input values are integers.
Input
N K A_1 A_2 \ldots A_N
- The first line contains two integers separated by a space: N, the number of socks, and K, the maximum allowable difference in color intensity for a pair.
- The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the color intensity of each sock.
Output
Print the maximum number of pairs of socks that Takahashi can make, in a single line.
Sample Input 1
6 2 1 3 5 2 8 7
Sample Output 1
3
Sample Input 2
10 3 1 5 9 13 17 2 6 10 14 18
Sample Output 2
5
Sample Input 3
15 100 50 200 350 500 120 80 210 340 510 130 75 220 360 490 140
Sample Output 3
6