小编fra*_*ank的帖子

假设您有 n 个排序的数字数组，您需要从每个数组中选择一个数字，以使 n 个所选元素之间的最小距离最大化。

例子：

arrays:
[0, 500]
[100, 350]
[200]

2<=n<=10每个数组都可以有~10^3-10^4元素。

在此示例中，最大化最小距离的最佳解决方案是选择数字：500、350、200 或 0、200、350，其中最小距离为 150，并且是每个组合的最大可能值。

我正在寻找一种算法来解决这个问题。我知道我可以对最大最小距离进行二分搜索，但我不知道如何确定是否存在最大最小距离至少为 d 的解决方案，以便二分搜索起作用。我在想动态编程可能会有所帮助，但还没有找到 dp 的解决方案。

当然，用 n 个元素生成所有组合效率不高。我已经尝试过回溯，但速度很慢，因为它尝试了每种组合。