java - 找到最窄间隔的算法，其中 m 将覆盖一组数字

Question

假设您有一个包含 n 个数字的列表。您可以选择 m 个整数(我们称整数为 a)。对于每个整数 a，删除包含范围 [a - x, a + x] 内的每个数字，其中 x 是一个数字.可以清除列表的x的最小值是多少？

例如，如果您的数字列表是

1 3 8 10 18 20 25

如果 m = 2，则答案为 x = 5。

您可以选择 5 和 20 这两个整数。这会清除列表，因为它会删除 [5-5, 5+5] 和 [20-5, 20+5] 之间的每个数字。

我该如何解决这个问题？我认为解决方案可能与动态规划有关。我不想要暴力方法解决方案。

代码会很有帮助，最好是 Java 或 C++ 或 C。

Answer 1

提示

假设你有列表

1 3 8 10 18 20 25

并想知道如果 x 等于 2 则需要多少组来覆盖该集合。

您可以通过选择第一个整数 1+x(1 是列表中的最小数字)以贪婪的方式解决此问题。这将涵盖最多 1+x+x=5 的所有元素。然后只需重复此过程，直到覆盖所有数字。

所以在这种情况下，下一个未覆盖的数字是 8，所以我们会选择 8+x=10 并覆盖第二组中直到 10+x=12 的所有数字。

同样，第三组将覆盖 [18,24]，第四组将覆盖 [25,29]。

这个 x 的值需要 4 组。这太多了，所以我们需要增加 x 并重试。

您可以使用二分法来确定确实涵盖 m 组中所有数字的 x 的最小值。