B. Micro-World

你有一个含有细菌的培养皿，正准备深入这个严酷的微观世界。但不幸的是，你附近没有显微镜，因此无法观察它们。 你知道培养皿中有 $n$ 个细菌，第 $i$ 个细菌的大小为 $a_i$。你还知道一个星际正整数常数 $K$。 第 $i$ 个细菌可以吞掉第 $j$ 个细菌，当且仅当 $a_i > a_j$ 且 $a_i lt.eq a_j + K$。被吞掉的 $j$-th 细菌会消失，但吞食的 $i$-th 细菌大小不变。细菌可以执行多次吞食操作。每次吞食操作中，任何细菌 $i$ 都可以吞食任何满足 $a_i > a_j$ 且 $a_i lt.eq a_j + K$ 的细菌 $j$。吞食操作依次进行。 例如，细菌大小序列为 $a = [ 101, 53, 42, 102, 101, 55, 54 ]$ 且 $K = 1$。一种可能的吞食序列是：$[ 101, 53, 42, 102, underline(101), 55, 54 ]$ $arrow.r$ $[ 101, underline(53), 42, 102, 55, 54 ]$ $arrow.r$ $[ underline(101), 42, 102, 55, 54 ]$ $arrow.r$ $[ 42, 102, 55, underline(54) ]$ $arrow.r$ $[ 42, 102, 55 ]$。最终培养皿中剩余 $3$ 个细菌。 由于你没有显微镜，只能猜测：当你最终找到显微镜时，培养皿中可能剩余的最少细菌数量是多少？ 第一行包含两个用空格分隔的正整数 $n$ 和 $K$（$1 lt.eq n lt.eq 2 dot.op 10^5$，$1 lt.eq K lt.eq 10^6$）——细菌数量和星际常数 $K$。 第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq 10^6$）——你拥有的细菌大小。 请输出一个整数——可能剩余的最少细菌数量。 第一个例子已在题面中说明。 在第二个例子中，最优的吞食序列是：$[ 20, 15, 10, 15, underline(20), 25 ]$ $arrow.r$ $[ 20, 15, 10, underline(15), 25 ]$ $arrow.r$ $[ 20, 15, underline(10), 25 ]$ $arrow.r$ $[ 20, underline(15), 25 ]$ $arrow.r$ $[ underline(20), 25 ]$ $arrow.r$ $[ 25 ]$。 在第三个例子中，没有任何细菌能吞食其他细菌。 ## Input 第一行包含两个用空格分隔的正整数 $n$ 和 $K$（$1 lt.eq n lt.eq 2 dot.op 10^5$，$1 lt.eq K lt.eq 10^6$）——细菌数量和星际常数 $K$。第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, dots.h, a_n$（$1 lt.eq a_i lt.eq 10^6$）——你拥有的细菌大小。 ## Output 请输出一个整数——可能剩余的最少细菌数量。 [samples] ## Note 第一个例子已在题面中说明。 在第二个例子中，最优的吞食序列是：$[ 20, 15, 10, 15, underline(20), 25 ]$ $arrow.r$ $[ 20, 15, 10, underline(15), 25 ]$ $arrow.r$ $[ 20, 15, underline(10), 25 ]$ $arrow.r$ $[ 20, underline(15), 25 ]$ $arrow.r$ $[ underline(20), 25 ]$ $arrow.r$ $[ 25 ]$。 在第三个例子中，没有任何细菌能吞食其他细菌。

Given: - A multiset $ A = \{a_1, a_2, \dots, a_n\} $ of positive integers representing bacterial sizes. - A positive integer constant $ K $. Definition: Bacteria $ i $ can swallow bacteria $ j $ if and only if: $$ a_i > a_j \quad \text{and} \quad a_i \leq a_j + K $$ Goal: Find the **minimum possible number of bacteria remaining** after any sequence of valid swallows (each swallow removes one bacterium; swallows can be performed in any order, and a bacterium may swallow multiple others sequentially). --- **Formal Problem Statement:** Let $ A $ be a multiset of $ n $ positive integers, and $ K \in \mathbb{Z}^+ $. Define a directed relation $ \rightarrow $ on $ A $: $$ a_i \rightarrow a_j \iff a_i > a_j \text{ and } a_i \leq a_j + K $$ A swallow sequence is a sequence of removals where each removed element $ a_j $ is swallowed by some remaining element $ a_i $ satisfying the above condition. We wish to find the **minimum number of elements** that can remain after any sequence of such swallows. --- **Key Insight:** This is equivalent to covering the multiset $ A $ with the **fewest possible "survivor" bacteria**, such that every non-survivor bacterium $ a_j $ is swallowed by some survivor $ a_i $, i.e., $ a_i \in (a_j, a_j + K] $. Equivalently: We want to partition $ A $ into as few subsets as possible, where in each subset, there is **one survivor** and all other elements can be "covered" by it — meaning each element $ x $ in the subset satisfies $ x \leq \text{survivor} \leq x + K $. To minimize the number of survivors, we can use a **greedy algorithm** on sorted data: 1. Sort the multiset $ A $ in non-decreasing order. 2. Traverse the sorted list and greedily assign each bacterium to the earliest possible survivor that can swallow it. But note: a survivor can swallow **multiple** bacteria, as long as each is in $ (x, x+K] $. Actually, the optimal strategy is: - Sort $ A $: $ b_1 \leq b_2 \leq \dots \leq b_n $ - Use a greedy grouping: Start with the smallest unassigned bacterium as a survivor. Then, all bacteria that are $ \leq \text{survivor} + K $ can be swallowed by it. - So, the survivor can "cover" a contiguous segment of bacteria from its own value up to its value + K. - Then move to the first bacterium not covered and make it the next survivor. This is equivalent to the **minimum number of intervals** of length $ K $ needed to cover all points, where each interval is $ [s, s+K] $ and must contain the point $ s $ (since the survivor must be present and swallow others). Actually, more precisely: Each survivor at value $ s $ can swallow any bacterium $ x $ such that $ s - K \leq x < s $. But since $ s $ must be in the set, and we are covering all elements, we can reframe: We want to cover all elements with the **minimum number of points** $ s_i $, such that for every element $ x $, there exists some $ s_i $ with: $$ x \in (s_i - K, s_i] $$ This is equivalent to: Cover the multiset $ A $ with intervals of the form $ (s - K, s] $, where $ s \in A $, and minimize the number of such intervals. This is a classic **interval covering problem** on the line. **Optimal greedy algorithm:** 1. Sort the array: $ b_1 \leq b_2 \leq \dots \leq b_n $ 2. Initialize: - survivors = 0 - last_survivor = -∞ 3. For each $ b_i $ in sorted order: - If $ b_i > \text{last\_survivor} + K $, then we need a new survivor at $ b_i $, because no previous survivor can swallow $ b_i $. - Otherwise, $ b_i $ can be swallowed by the last survivor. Why? Because if the last survivor was placed at $ s $, then it can swallow any $ x \in (s - K, s] $. But since we process in increasing order, and we place a survivor at $ b_i $ only when $ b_i > \text{last\_survivor} + K $, then: - The previous survivor $ s $ can swallow all $ x \leq s + K $. - So if $ b_i \leq s + K $, it can be swallowed. - If $ b_i > s + K $, then even the largest value $ s + K $ is less than $ b_i $, so $ s $ cannot swallow $ b_i $, and we need a new survivor. Thus, the algorithm: ```plaintext Sort A survivors = 0 last_s = -inf for each a in sorted(A): if a > last_s + K: survivors += 1 last_s = a ``` Then output `survivors`. --- **Final Formal Output:** Let $ A = \{a_1, a_2, \dots, a_n\} $ be a multiset of positive integers, and $ K \in \mathbb{Z}^+ $. Sort $ A $ in non-decreasing order: $ b_1 \leq b_2 \leq \dots \leq b_n $. Define: $$ \text{min\_survivors} = \min \left\{ m \in \mathbb{N} \,\middle|\, \exists \, s_1 \leq s_2 \leq \dots \leq s_m \in A \text{ s.t. } \forall i \in [n], \exists j \in [m] \text{ with } b_i \in (s_j - K, s_j] \right\} $$ This minimum is computed by the greedy algorithm: $$ \boxed{ \begin{aligned} &\text{Sort } b_1 \leq b_2 \leq \dots \leq b_n \\ &\text{Set } \text{count} = 0, \text{ last} = -\infty \\ &\text{For } i = 1 \text{ to } n: \\ &\quad \text{If } b_i > \text{last} + K: \\ &\quad\quad \text{count} \gets \text{count} + 1 \\ &\quad\quad \text{last} \gets b_i \\ &\text{Return } \text{count} \end{aligned} } $$