← 返回比赛

已结束 GESP挑战赛#33

← 上一题下一题 →

A7447 | $水晶整理$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

$Sherry$ 购买了一批魔法水晶。一共有 $n$ 块水晶，第 $i$ 块水晶的能量值为 $a_i$。此外，根据魔法水晶的种类，会有一个确定的环境系数 $k$。 如果第 $i$ 块水晶的能量值满足 $a_i>a_j$ 且 $a_i\le a_j+k$，那么第 $i$ 块水晶就可以吸收第 $j$ 块水晶。吸收后，第 $j$ 块水晶会消失，但第 $i$ 块水晶的能量值不会发生改变。 每一次吸收操作可以任选两块符合吸收条件的水晶，每块水晶都可以进行多次吸收操作。吸收操作依次进行。 $Sherry$ 现在拿到了水晶清单，请你帮 $Sherry$ 算一算，经过若干次吸收操作后，最少可能剩下多少块水晶。

输入格式

第一行输入两个正整数 $n,k$，分别表示水晶数量和环境系数。 第二行输入 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示每个水晶的能量值。

输出格式

输出一个整数，表示收到水晶时可能剩下的最少水晶数量。

输入输出样例

输入 #1

7 1
101 53 42 102 101 55 54

输出 #1

输入 #2

6 5
20 15 10 15 20 25

输出 #2

输入 #3

7 1000000
1 1 1 1 1 1 1

输出 #3

C++ 编辑器

输入

输出