CF985E Pencils and Boxes

Mishka 收到了一个多彩铅笔作为生日礼物！不幸的是，他生活在一个单色的世界里，那里的一切都是同一种颜色，只有饱和度不同。这个铅笔盒可以表示为一个长度为 $n$ 的整数序列 $a_{1},a_{2},...,a_{n}$，其中每个数表示每支铅笔颜色的饱和度。现在，Mishka 想要把盒子里的铅笔整理好。他有无限多个空盒子可以使用。他希望按照以下方式将铅笔放入盒子： - 每支铅笔恰好属于一个盒子； - 每个非空盒子里至少有 $k$ 支铅笔； - 如果第 $i$ 支和第 $j$ 支铅笔在同一个盒子里，那么 $|a_{i}-a_{j}| \leq d$，其中 $|x|$ 表示 $x$ 的绝对值。注意，反过来并不要求成立，也就是说可能存在 $|a_{i}-a_{j}| \leq d$ 但它们属于不同盒子的情况。 请你帮助 Mishka 判断是否存在一种分配方式，使得所有铅笔都能被放入盒子并满足上述所有条件。如果存在，输出 "YES"；否则输出 "NO"。

第一行包含三个整数 $n$、$k$ 和 $d$（$1 \leq k \leq n \leq 5 \cdot 10^{5}$，$0 \leq d \leq 10^{9}$），分别表示铅笔的数量、每个非空盒子的最小容量，以及同一盒子内任意两支铅笔饱和度的最大差值。 第二行包含 $n$ 个整数 $a_{1},a_{2},...,a_{n}$（$1 \leq a_{i} \leq 10^{9}$），表示每支铅笔的颜色饱和度。

如果存在一种分配方式满足所有条件，输出 "YES"；否则输出 "NO"。

在第一个样例中，可以将铅笔分成 $2$ 个盒子，每个盒子里有 $3$ 支铅笔，分配方式任意。你也可以把所有铅笔都放在同一个盒子里，因为任意两支铅笔的饱和度差不会超过 $10$。 在第二个样例中，你可以把饱和度为 $[4,5,3,4]$ 的铅笔分成 $2$ 个盒子，每个盒子 $2$ 支铅笔，剩下的铅笔放到另一个盒子里。 由 ChatGPT 4.1 翻译