A128503.水晶整理
普及-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
Sherry 购买了一批魔法水晶。一共有 n 块水晶,第 i 块水晶的能量值为 ai。此外,根据魔法水晶的种类,会有一个确定的环境系数 k。
如果第 i 块水晶的能量值满足 ai>aj 且 ai≤aj+k,那么第 i 块水晶就可以吸收第 j 块水晶。吸收后,第 j 块水晶会消失,但第 i 块水晶的能量值不会发生改变。
每一次吸收操作可以任选两块符合吸收条件的水晶,每块水晶都可以进行多次吸收操作。吸收操作依次进行。
Sherry 现在拿到了水晶清单,请你帮 Sherry 算一算,经过若干次吸收操作后,最少可能剩下多少块水晶。
输入格式
第一行输入两个正整数 n,k,分别表示水晶数量和环境系数。
第二行输入 n 个整数 a1,a2,⋯,an,表示每个水晶的能量值。
输出格式
输出一个整数,表示收到水晶时可能剩下的最少水晶数量。
输入输出样例
输入#1
7 1 101 53 42 102 101 55 54
输出#1
3
输入#2
6 5 20 15 10 15 20 25
输出#2
1
输入#3
7 1000000 1 1 1 1 1 1 1
输出#3
7
说明/提示
数据范围
1≤n≤2×105
1≤k≤106
1≤ai≤106
输入解题思路,AI测评打分。不知道怎么写?