Problem2075--分堆

2075: 分堆

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 182  Solved: 58
[Status] [Submit] [Creator:]

Description

将 n 个整数分成若干堆,要求每堆数中的任意两个整数间相差不超过 k(即要求每一堆数里面的 最大值 - 最小值 之差 ≤ k)。

问:最少分成几堆?

Input

第一行包含两个整数 n 和 k(1 ≤ n ≤ 105, 1 ≤ k ≤ 109)。

第二行包含 n 个整数,两两之间以一个空格分隔。每个整数均为不超过 109 的正整数。

Output

输出一个整数,表示满足每一堆的最大值与最小值只差不超过 k 的情况下,最小的堆数。

Sample Input Copy

【样例输入1】
5 3
1 5 3 2 4
【样例输出1】
2
【样例输入2】
5 1
1 5 3 2 4
【样例输出2】
3
【样例输入3】
5 4
1 5 3 2 4
【样例输出3】
1

HINT

【样例解释】
样例1:存在多种最少分组方案,其中一种是:第 1 堆放数字 1,2,3,4;第 2 堆放数字 5。
样例2:存在多种最少分组方案,其中一种是:第 1 堆放数字 1,2;第 2 堆放数字 3,4;第 3 堆放数字 5。
样例3:将所有数字放在同一堆即为最少分组方案。
【数据规模与约定】
设 A 为 n 个数的最大值,则:
· 对于 30% 的数据,1 ≤ n ≤ 100, 1 ≤ k,A ≤ 1000
· 对于 60% 的数据,1 ≤ n ≤ 1000, 1 ≤ k,A ≤ 106
· 对于 100% 的数据,1 ≤ n ≤ 105, 1 ≤ k,A ≤ 109

Source/Category