CF940A Points on the line

我们没有测试用例。一个大型奥林匹克竞赛即将到来。但出题人的首要任务应该是为比赛再添加一道题目。 一组在数轴上的点的多重集的直径，定义为该集合中任意两点之间的最大距离。例如，多重集 $ \{1,3,2,1\} $ 的直径为 $2$。 只包含一个点的多重集的直径为 $0$。 给定 $n$ 个在数轴上的点。你需要移除最少数量的点，使得剩下点的多重集的直径不超过 $d$。

第一行包含两个整数 $n$ 和 $d$（$1 \leq n \leq 100, 0 \leq d \leq 100$），分别表示点的数量和允许的最大直径。 第二行包含 $n$ 个用空格分隔的整数（$1 \leq x_{i} \leq 100$），表示这些点的坐标。

输出一个整数，表示你需要移除的最少点数。

在第一个测试用例中，最优策略是移除坐标为 $4$ 的点。剩下的点坐标为 $1$ 和 $2$，此时直径为 $2-1=1$。 在第二个测试用例中，直径为 $0$，因此无需移除任何点。 在第三个测试用例中，最优策略是移除坐标为 $1$、$9$ 和 $10$ 的点。剩下的点坐标为 $3$、$4$ 和 $6$，此时直径为 $6-3=3$。 由 ChatGPT 4.1 翻译