A128503.水晶整理

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

SherrySherry 购买了一批魔法水晶。一共有 nn 块水晶,第 ii 块水晶的能量值为 aia_i。此外,根据魔法水晶的种类,会有一个确定的环境系数 kk

如果第 ii 块水晶的能量值满足 ai>aja_i>a_jaiaj+ka_i\le a_j+k,那么第 ii 块水晶就可以吸收第 jj 块水晶。吸收后,第 jj 块水晶会消失,但第 ii 块水晶的能量值不会发生改变。

每一次吸收操作可以任选两块符合吸收条件的水晶,每块水晶都可以进行多次吸收操作。吸收操作依次进行。

SherrySherry 现在拿到了水晶清单,请你帮 SherrySherry 算一算,经过若干次吸收操作后,最少可能剩下多少块水晶。

输入格式

第一行输入两个正整数 n,kn,k,分别表示水晶数量和环境系数。

第二行输入 nn 个整数 a1,a2,,ana_1,a_2,\cdots,a_n,表示每个水晶的能量值。

输出格式

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

输入输出样例

  • 输入#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

说明/提示

数据范围

1n2×1051\le n\le 2\times 10^{5}

1k1061\le k\le 10^{6}

1ai1061\le a_{i}\le 10^{6}

输入解题思路,AI测评打分。不知道怎么写?

首页