假设你得到了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 个元素的组合效率不高。我已经尝试过回溯，但它很慢，因为它尝试了每种组合。
n≤ 10 表明我们可以对 n 进行指数依赖。这是 一个 O(2 n mn)-时间算法，其中 m 是 阵 列。
我想到的动态编程方法是，对于每个子集 数组，计算所有对(最大数量，最小距离) 有效边界，我们必须从每个数字中选择一个数字 子集中的数组。我所说的有效边界是指如果我们有 两对 (A， B) ≠ (C， D) ≤ C 和 B ≥ D，则 (C， D) 不打开 高效的前沿。我们希望对这些边界进行排序 快速合并。
空子集的基本情况很简单：有一对，(最小值 距离 = ∞，最大数量 = −∞)。
对于数组的每个非空子集，按某种顺序扩展 包含顺序，我们为子集中的每个数组计算边界， 表示该数组贡献的解决方案的子集 最大数量。然后我们合并这些边界。(天真地，这让我们付出了代价 日志 n 的另一个因素，可能不值得麻烦避免 鉴于 n ≤ 10，但我们可以通过在 开始启用将来的合并以使用存储桶。
从数组子集和另一个数组构造新边界 还涉及合并。我们在 边界(即最小最大数量)和迭代器在 数组(即最少数量)。虽然两个迭代器都没有结束，
- 发出候选对(最小(最小距离，数组数 − 最大值) 编号)，数组编号)。
- 如果最小值小于或等于最小距离，则递增 前沿迭代器。如果最小值小于或等于数组编号 − 最大数量，递增数组迭代器。
剔除候选对，只留下有效边界。有 一种在代码中执行此操作的优雅方法，解释起来更麻烦。
我将给出一种算法，对于给定的距离d，将输出是否可以进行任何一对选定数字之间的距离至少为d的选择。然后，您可以二元搜索算法输出"YES"的最大d，以找到问题的答案。
假设d给出最小距离。这是算法：
for every permutation p of size n do:
last := -infinity
ok := true
for p_i in p do:
x := take the smallest element greater than or equal to last+d in the p_i^th array (can be done efficiently with binary search).
if no such x was found; then
ok = false
break
end
last = x
done
if ok; then
return "YES"
end
done
return "NO"
因此，我们暴力破解数组的顺序。然后，对于每个可能的顺序，我们使用贪婪的方法从每个数组中选择元素，遵循顺序。例如，以你给出的示例为例：
arrays:
[0, 500]
[100, 350]
[200]
并假设d = 150.对于置换1 3 2，我们首先从第一个数组中取 0，然后我们找到第 3 个数组中大于或等于 0+150 的最小元素(它是 200)，然后我们找到第二个数组中大于或等于 200+150 的最小元素(它是 350)。由于我们可以从每个数组中找到一个元素，因此算法输出"YES"。 但例如，对于d = 200，算法将输出"NO"，因为没有一个可能的排序会导致成功的选择。
上述算法的复杂性O(n! * n * log(m))其中m是数组中的最大元素数。我相信这就足够了，因为n很小。(对于m = 10^4，10! * 10 * 13 ~ 5*10^8。它可以在现代 CPU 上计算不到一秒。
让我们看一个具有最佳选择的示例，x(水平数组 A、B、C、D)：
A x
B b x b
C x c
D d x
我们基于范围的递归可以是：设f(low, excluded)表示excluded中没有元素的子集的两个选定元素(从数组 1 到n)之间的最大最近距离，其中low是最低选择的元素。然后：
(1)
f(low, excluded) when |excluded| = n-1:
max(low)
for low in the only permitted array
(2)
f(low, excluded):
max(
min(
a - low,
f(a, excluded')
)
)
for a ≥ low, a not in excluded'
where excluded' = excluded ∪ {low's array}
我们可以限制a.对于我们所能达到的最大值的一件事是
(3)
m = (highest - low) / (n - |excluded| - 1)
这意味着a不需要高于low + m。
其次，我们可以存储所有f(a, excluded')的结果，按excluded'键(我们有 2^10 个可能的键)，每个键都位于按a排序的装饰二叉树中。修饰将是右子树中可实现的最高结果，这意味着我们可以在对数时间内找到所有f(v, excluded'), v ≥ a的最大值。
后者建立了支配关系，显然，我们在更大的a和更大的f(a, excluded')中都得到了认同，以便最大化(2)中的min功能。在中间选择一个a，我们可以使用二进制搜索。如果我们有：
a - low < max(v, excluded'), v ≥ a
where max(v, excluded') is the lookup
for a in the decorated tree
然后我们向右看，因为max(v, excluded)表示右边有更好的答案，a - low也更大。
如果我们有：
a - low ≥ max(v, excluded), v ≥ a
然后我们记录这个候选人并向左看，因为向右看，答案固定在max(v, excluded)，因为a - low不会减少。
为了对范围进行二分搜索，[low, low + m](参见(3))，而不是在一开始就合并和标记所有数组，我们可以将它们分开，并比较当前允许从中选择a的每个数组中最接近的候选数组mid。(树的结果混合，按子集键控。(这部分的流程对我来说并不完全清楚。
这种方法的最坏情况，因为n = C是恒定的
O(C * array_length * 2^C * C * log(array_length) * log(C * array_length))
C * array_length is the iteration on low
Each low can be paired with 2^C inclusions
C * log(array_length) is the separated binary-search
And log(C * array_length) is the tree lookup
简化：
= O(array_length * log^2(array_length))
尽管在实践中，可能会有许多死胡同分支提前退出，无法进行完整选择。
如果不清楚，迭代位于选择中的固定最低元素上。换句话说，我们希望为所有不同的low(和excludeds)提供最佳f(low, excluded)。对于自下而上，我们将从最高值向下迭代，以便在迭代时存储a结果。