Match Points
题意翻译
## 题目描述
给你一个在数轴上的点集$x_1, x_2, \dots, x_n$。
每两个点$i$,$j$可以在满足以下情况的时候相连:
- 点$i$和点$j$均未与其他点相连;
- $\left| x_i - x_j \right| \geq z$.
那么请你求出最多可以连接多少点对?
## 输入输出格式
### 输入格式:
第一行包含两个整数$n$和$z\;(2 \leq n \leq 2 \cdot 10^5,\,1 \leq z \leq 10^9)$ —— 分别代表点的数量和连接点对时最长距离。
第二行包含$n$个整数$x_1, x_2, \dots, x_n\;(1 \leq x_i \leq 10^9)$.
### 输出格式:
输出一个整数,代表最大能够互相连接的点对数量。
## 输入输出样例:
略...
## 说明:
样例1中,可以连接1号点和2号点($\left| 3 - 1 \right| \geq 2$),3号点和4号点($\left| 7 - 3 \right| \geq 2$).
样例2中,可以连接1号点和3号点($\left|5 - 10\right| \geq 5$).
题目描述
You are given a set of points $ x_1 $ , $ x_2 $ , ..., $ x_n $ on the number line.
Two points $ i $ and $ j $ can be matched with each other if the following conditions hold:
- neither $ i $ nor $ j $ is matched with any other point;
- $ |x_i - x_j| \ge z $ .
What is the maximum number of pairs of points you can match with each other?
输入输出格式
输入格式
The first line contains two integers $ n $ and $ z $ ( $ 2 \le n \le 2 \cdot 10^5 $ , $ 1 \le z \le 10^9 $ ) — the number of points and the constraint on the distance between matched points, respectively.
The second line contains $ n $ integers $ x_1 $ , $ x_2 $ , ..., $ x_n $ ( $ 1 \le x_i \le 10^9 $ ).
输出格式
Print one integer — the maximum number of pairs of points you can match with each other.
输入输出样例
输入样例 #1
4 2
1 3 3 7
输出样例 #1
2
输入样例 #2
5 5
10 9 5 8 7
输出样例 #2
1
说明
In the first example, you may match point $ 1 $ with point $ 2 $ ( $ |3 - 1| \ge 2 $ ), and point $ 3 $ with point $ 4 $ ( $ |7 - 3| \ge 2 $ ).
In the second example, you may match point $ 1 $ with point $ 3 $ ( $ |5 - 10| \ge 5 $ ).