A108430.返程拼车
普及-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
比赛结束后,同学们要从学校回家。把学校看作数轴上的位置 0,第 i 位同学的家在数轴上的位置 xi(整数,可为负,表示在学校左侧)。
打车规则如下:
- 一辆车最多载 2 位同学;
- 两位同学可以拼车,当且仅当他们两家之间的距离不超过 D,即 ∣xi−xj∣≤D;
- 若两位同学拼车,他们一起从学校出发,司机可以按任意顺序送到两家(题目只关心是否允许拼车与车的数量,不计路程)。
问:最少需要多少辆车,才能让所有同学都回家?
输入格式
第一行两个整数 n,D。
第二行 n 个整数 x1,x2,…,xn。
输入输出样例
输入#1
6 2 -3 -1 1 2 5 6
输出#1
3
说明/提示
- 1≤n≤2×105
- 0≤D≤109
- −109≤xi≤109