宽敞集合 - المسألة

Ada 和 John 是好朋友。由于感到无聊，Ada 请 John 为她解决一个谜题。

如果一个集合 $S$ 中任意两个不同元素之间的绝对差值至少为 $K$，即对于所有 $x, y \in S$ 且 $x \neq y$，都有 $|x - y| \geq K$，则称该集合为“宽敞的”（spacious）。

Ada 有一个包含 $N$ 个不同整数的列表 $\mathbf{A}$ 和一个整数 $K$。对于每个 $\mathbf{A}_i$，她请 John 找出由 $\mathbf{A}$ 中的元素组成的、包含 $\mathbf{A}_i$ 且为宽敞集合的子集的最大大小。

注意：集合 $S_i$ 不需要由列表中的连续元素组成。

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $K$。下一行包含 $N$ 个整数 $\mathbf{A}_1, \mathbf{A}_2, \dots, \mathbf{A}_N$。

对于每个测试用例，输出一行 Case #x: y1 y2 ... yN，其中 $x$ 是测试用例编号（从 1 开始），$y_i$ 是由 $\mathbf{A}$ 中元素组成的、包含 $\mathbf{A}_i$ 的宽敞集合的最大大小。

$1 \leq T \leq 100$ $-10^9 \leq \mathbf{A}_i \leq 10^9$，对于所有 $i$。 $\mathbf{A}_i \neq \mathbf{A}_j$，对于所有 $i \neq j$。

子任务 1 $1 \leq N \leq 10$ $1 \leq K \leq 100$

子任务 2 $1 \leq K \leq 10^9$ 对于最多 15 个测试用例： $1 \leq N \leq 10^5$ 对于其余测试用例： $1 \leq N \leq 10^3$

2
3 2
1 2 3
6 4
2 7 11 19 5 3

Case #1: 2 1 2
Case #2: 4 4 4 4 3 4

在样例 1 中，宽敞集合不能同时包含 1 和 2，也不能同时包含 2 和 3。这意味着 $S_2 = \{2\}$，而使用 $S_1 = S_3 = \{1, 3\}$ 可以使它们达到最大大小。

在样例 2 中，最大大小的可能集合为： $S_1 = S_2 = S_3 = S_4 = \{2, 7, 11, 19\}$ $S_5 = \{11, 19, 5\}$ * $S_6 = \{7, 11, 19, 3\}$

QOJ.ac