P17756 「RSOI-3E」集合构造 / set

题目来源：【HT-126-Div.2】核桃 CSP-S 组模拟赛

给定一个长度为 $n$ 的正整数序列 $A = \{A_1, A_2, \dots, A_n\}$，以及非负整数 $k$ 和正整数 $d$。 你可以构造一个正整数多重集合 $B$，要求满足 $|B| \le k$（即集合 $B$ 中最多包含 $k$ 个元素，且元素可以任意指定）。 令集合 $S = A \cup B$。你需要从 $S$ 中选出一个子集 $T \subseteq S$，使得 $T$ 中的元素在按严格递增顺序排列后 $t_1 < t_2 < \dots < t_m$，能够满足： - 对于任意 $1 \le i < m$，均有 $t_{i+1} - t_i \le d$。 求 $|T|$ 的最大值（即 $m$ 的最大值）。

输入共两行。 第一行，三个整数 $n, k, d$。 第二行，包含 $n$ 个正整数表示序列 $A_i$。

输出共一行，一个整数表示 $|T|$ 的最大值。

**【样例解释 #1】** 对于样例 #1，原序列 $A$ 去重并排序后为 $\{1, 4, 8, 9, 13\}$。 我们可以选择 $A$ 中的子集 $\{4, 8, 9\}$，并构造集合 $B = \{6\}$（只使用了 $1$ 个元素，满足 $|B| \le 1$）。 此时 $T = \{4, 6, 8, 9\}$，排序后相邻两项的差值分别为 $2, 2, 1$，均不超过 $d=2$。集合 $T$ 的大小为 $4$。 **【样例解释 #2】** 对于样例 #2，原序列 $A$ 去重排序后为 $\{2, 4, 5, 10, 11, 15, 16, 20\}$。 选取 $A$ 中的 $\{2, 4, 5, 10, 11, 15, 16\}$，并令 $B = \{8, 14\}$。 此时 $T = \{2, 4, 5, 8, 10, 11, 14, 15, 16\}$，相邻差值最大为 $3$，大小为 $9$。 **【数据范围】** **本题采用捆绑测试。** 对于所有测试数据，保证： $1 \le n \le 10^5$，$0 \le k \le 10^9$，$1 \le d, A_i \le 10^9$。 |子任务编号 |$n\le$ |特殊性质 |分值 | |:-------:|:--------:|:-----:|:--:| |1|$10^2$ |$k=0$ |$15$| |2|$10^3$|无 |$15$| |3|$10^5$|$k=0$ |$20$| |4|$10^5$|$d=1$ |$20$| |5|$10^5$|无 |$30$|