Problem 4B. 细菌吞噬

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 4B. 细菌吞噬

时间限制:2s

空间限制:256MB

Description

你有一个装有细菌的培养皿,但不幸的是,你身边没有显微镜,所以无法观察它们。

你知道培养皿中有 \(n\) 个细菌,而第 \(i\) 个细菌的大小是 \(a_i\) 。你还知道一个正整数常数 \(K\) 。

当且仅当 \(a_i > a_j\) 和 \(a_i \le a_j + K\) 时,第 \(i\) 个细菌可以吞下第 \(j\) 个细菌。第 \(j\) 个细菌会消失,但第 \(i\) 个细菌的大小不会改变。细菌可以进行多次吞咽。在每次吞咽操作中,如果有 \(a_i > a_j\) 和 \(a_i \le a_j + K\) ,任何细菌 \(i\) 都可以吞咽任何细菌 \(j\) 。吞咽操作一个接一个。

例如,大小为 \(a=[101, 53, 42, 102, 101, 55, 54]\) 和 \(K=1\) 的细菌序列。其中一个可能的吞咽序列是 \([101, 53, 42, 102, \underline{101}, 55, 54]\) \(\to\) \([101, \underline{53}, 42, 102, 55, 54]\) \(\to\) \([\underline{101}, 42, 102, 55, 54]\) \(\to\) \([42, 102, 55, \underline{54}]\) \(\to\) \([42, 102, 55]\) .总共有 \(3\) 个细菌留在培养皿中。

请找到培养皿中细菌的最少数量是多少。

Input Format

第一行包含两个空格分隔的正整数 \(n\) 和 \(K\) - 细菌数量和常数 \(K\) 。

第二行包含 \(n\) 空格分隔的整数 \(a_1, a_2, \dots, a_n\) - 细菌的大小。

Output Format

输出一行一个整数 - 最小可能的可以保留的细菌数量。

Input Example #1:

7 1
101 53 42 102 101 55 54

Output Example #1:

3

Input Example #2:

6 5
20 15 10 15 20 25

Output Example #2:

1

Input Example #3:

7 1000000
1 1 1 1 1 1 1

Output Example #3:

7

Data Range

\(1 \le n \le 2 \cdot 10^5\) , \(1 \le K \le 10^6\) , \(1 \le a_i \le 10^6\) 。

Note

第一个例子在问题陈述中已解释。

在第二个例子中,最佳可能序列是: \([20, 15, 10, 15, \underline{20}, 25]\) \(\to\) \([20, 15, 10, \underline{15}, 25]\) \(\to\) \([20, 15, \underline{10}, 25]\) \(\to\) \([20, \underline{15}, 25]\) \(\to\) \([\underline{20}, 25]\) \(\to\) \([25]\) 。

在第三个例子中,没有细菌可以吞噬其他细菌。

2023秋 悬赏令第四周

未参加
状态
已结束
规则
OI
题目
6
开始于
2023-10-29 18:30
结束于
2023-11-05 00:00
持续时间
149.5 小时
主持人
参赛人数
83