我有一个编号为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)。
到目前为止,我想出了这个方案:
- 元素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];
这个方法可以给出我所举的例子的正确答案,但我不确定它在每种情况下都适用,并且我不知道如何定义那些无法实现或元素之间距离可以是任意值的情况。