A108430.返程拼车

普及-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

比赛结束后,同学们要从学校回家。把学校看作数轴上的位置 00,第 ii 位同学的家在数轴上的位置 xix_i(整数,可为负,表示在学校左侧)。

打车规则如下:

  • 一辆车最多载 2 位同学;
  • 两位同学可以拼车,当且仅当他们两家之间的距离不超过 DD,即 xixjD|x_i-x_j|\le D
  • 若两位同学拼车,他们一起从学校出发,司机可以按任意顺序送到两家(题目只关心是否允许拼车与车的数量,不计路程)。

问:最少需要多少辆车,才能让所有同学都回家?

输入格式

第一行两个整数 n,Dn,D

第二行 nn 个整数 x1,x2,,xnx_1,x_2,\dots,x_n

输入输出样例

  • 输入#1

    6 2
    -3 -1 1 2 5 6

    输出#1

    3

说明/提示

  • 1n2×1051\le n\le 2\times 10^5
  • 0D1090\le D\le 10^9
  • 109xi109-10^9\le x_i\le 10^9
首页