用绝对差替换两个元素，并在数组中生成最小可能的元素

Question

我有一个大小为n的数组，我可以在它上应用任意数量的操作(包括零)。在一个操作中，我可以将任意两个元素替换为两个元素的绝对差异。我们必须找到可以使用该操作生成的最小可能元素。(n<1000)

下面是一个操作如何工作的示例。设数组为1,3,4。对1,3的运算给出2,4作为新的数组。

例:2 6 11 3 => ans =0

这是因为11-6 =5和5-3 =2和2-2 =0。

Ex: 20 6 4 => ans =2

例:2 6 10 14 => ans =0

例:2 6 10 => ans =2

有人能告诉我如何处理这个问题吗？

编辑：

我们可以使用递归生成所有可能的情况，并从中选择最小的元素。这将具有O(n^2 !)的复杂性。

我尝试过的另一种方法是对数组进行排序，然后进行递归调用，从0或1开始，对所有连续元素应用这些操作。这将继续下去，直到它们只是数组中剩下的一个元素为止，我们可以在递归的任意点返回最小值。这将具有O(n^2)的复杂性，但不一定给出正确的答案。

例:2 6 10 15 => (4 5)和(2 4 15) => (1)和(2 15)和(2 11) => (13)和(9)。这其中的最小值是1，这就是答案。

Answer 1

当您为操作选择两个元素时，从较大的元素中减去较小的元素。因此，如果选择1和7，结果是7-1= 6。

现在有了2，6和8，你可以做：

8-2 -> 6然后6-6=0

您也可以这样写:8-2-6=0。

让我们考虑不同的操作:你可以取两个元素，用它们的和或它们的差来代替它们。

尽管可以使用新操作获得完全不同的值，但最接近0的元素的绝对值将与使用旧操作的绝对值完全相同。

首先，让我们尝试使用新的操作来解决这个问题，然后我们将确保答案确实与使用旧操作相同。

您要做的是选择两个非相交的初始数组子集，然后从第一个集合中的所有元素和第一个元素中减去第二个元素的和。您希望找到两个这样的子集，其结果最接近于0。这是一个NP问题，可以用类似于O(n *和的所有元素的)中的背包问题的伪多项式算法有效地解决它。

初始数组中的每个元素都可以属于正集(从其中减去的集合)、负集(可以减去和)，也可以不属于它们。用不同的话说:每个元素都可以添加到结果中，从结果中减去，或者保持不变。假设我们已经使用从第一个元素到第一个元素的元素计算了所有可获得的值。现在我们考虑I+1元素.我们可以取任何一个可以得到的值，然后增加它，或者用I+1元素的值来减少它。在对所有元素执行这些操作之后，我们从该数组中获得所有可能的值。然后我们选择一个离0最近的。

现在更难的是，为什么它总是一个正确的答案？让我们考虑正集和负集，从中得到极小的结果。我们希望使用初始操作来实现这一目标。假设负集合中的元素多于正集合中的元素(否则交换它们)。

如果我们在正集合中只有一个元素，在负集合中只有一个元素，那该怎么办？那么，它们的差的绝对值等于我们对它的运算得到的值。

如果我们在正集合中有一个元素，在负集合中有两个元素呢？

1)负元素中有一个小于正元素，我们只需对其进行运算即可。它的结果是正集中的一个新元素。那我们就有上一个案子了。

( 2)两种负元素均小于正元素。如果我们从负集合中去掉更大的元素，结果就接近于0，所以这种情况是不可能发生的。

假设我们在正集中有n个元素，在负集(n <= m)中有m个元素，我们可以通过一些运算得到它们的和差的绝对值(我们称之为x)。现在，让我们向负集合添加一个元素。如果添加新元素之前的差值为负值，则将其减少任何其他数字使其变小，这比0更远，因此不可能。所以差别肯定是肯定的。然后我们可以使用x上的运算和新元素来得到结果。

现在第二个例子:假设我们在正集中有n个元素，在负集中有m个元素(n < m)，我们可以使用一些运算得到它们的和的差的绝对值(同样我们称之为x)。现在我们将新元素添加到正集合中。同样，差一定是负的，所以x在负集合中。然后对x和新元素进行运算，得到结果。

通过归纳，我们可以证明答案总是正确的。