找出给定条件下元素之间的最大距离

Question

我有一个编号为1到N的元素列表，这些元素可以放在从1开始的数轴上的位置上。我还有一些对这些元素的限制：

- 元素1位于位置1，元素N必须在元素N-1的位置之后（即元素2可以在位置1，元素3可以在位置7，元素4可以在位置8（但不能在位置5））。 - 一些元素必须在数轴上彼此之间保持一定的距离。 - 一些元素在数轴上必须至少相隔一定距离。

我的目标是返回一个整数，表示元素1和元素N之间的最大跨度。如果无法排列，则返回-1；如果元素可以任意距离分开，则返回-2。

给出：

- 元素数量 - withinArray[][]，其中withinArray[x][y]表示x和y元素在数轴上必须保持的距离。任何零值表示没有限制。 - atLeastArray[][]，其中atLeastArray[x][y]表示x和y元素在数轴上必须相隔的距离。任何零值表示没有限制。

例如输入：4个元素，withinArray[1][3] = 10，withinArray[2][4] = 20，atLeastArray[2][3] = 3（所有其他数组值都为零）。

那么这个输入的返回值将是27（元素1在位置1，元素2在位置8，元素3在位置11，元素4在位置28）。

到目前为止，我想出了这个方案：

for (int i = 1; i < n; i++) {
    for (int j = 1; j < atLeastArray.length; j++) 
        if (j == i)
            positions[i] = positions[j] - atLeastArray[i][j];
    for (int j = 1l j < withinArray.length; j++) 
        if (j == i) 
            positions[j] = positions[i] + withinArray[i][j];
}
return positions[n] - positions[1];

这个方法可以给出我所举的例子的正确答案，但我不确定它在每种情况下都适用，并且我不知道如何定义那些无法实现或元素之间距离可以是任意值的情况。

- user1877515

---

听起来像是线性规划。 - nhahtdh

Answer 1

让我们从线性规划的角度来考虑这个问题。我们有变量x_1，...，x_n和一堆形如x_i <= x_(i+1)，x_i - x_j <= w_{ij}和x_i - x_j >= a_(ij)的约束条件。

注意当我们对一个变量进行傅里叶-莫扎金消元时会发生什么---也就是在它出现的每个方程中隔离它，形成两组不等式，比如说x_i <= foo_k和x_i >= bar_l，然后删除涉及x_i的所有约束条件，并用每个k和l的约束条件bar_l <= foo_k替换它们。

你会得到更多与之前相同形式的约束条件！请注意，如果你知道x_i - x_j <= a和x_i - x_j <= b，你可以得出x_i - x_j <= min(a,b)并忘记之前的两个约束条件。因此，你永远不需要超过n^2个约束条件。

所以只需消除除x_1和x_n之外的所有变量。最后你将有两个约束条件，即x_n - x_1 >= a和x_n - x_1 <= b。检查a <= b并且b不是无穷大，你就可以了。

哦，如果有人能教我如何在这个东西上写数学公式，我会很感激的 :)

- tmyklebu