分区阵列的差异很小

Question

给定N整数的数组A。我需要找到X，以便以下2个值(A[1] * A[2] * ... * A[X])和(A[X+1] * A[X+2] * ... * A[N])之间的差异最小，即我需要最小化| (A[1] * A[2] * ... * A[X]) - (A[X+1] * A[X+2] * ... * A[N]) |，如果有多个这样的值x的值，请打印最小的一个。

。

约束： -

• 1＆lt; = N＆lt; = 10^5

• 1＆lt; = A[i]＆lt; = 10^18。

我无法找到有效解决此问题的方法。解决这个问题的最佳方法应该是什么。是否有任何特殊算法用于乘以大量数字。

Answer 1

这个想法是使用前缀和后缀产品的形式。

让：

1. pre[i] = A[1] * A[2] * ... A[i]和
2. suf[i] = A[i] * A[i + 1] * ... A[N]

您可以在O(n(时间中计算这些数组，为：

• pre[i] = A[i] * pre[i - 1]带有pre[1] = A[i]和

• suf[i] = A[i] * suf[i + 1] with suf[N] = A[n]

然后，从i = 1到n，并计算最大：

abs(pre[i] - suf[i + 1])

观察pre[i] - suf[i + 1]与：

相同

(A[1] * A[2] * ... * A[i]) - (A[i + 1] * A[i + 2] ... * A[N])

这正是您要计算的。

Answer 2

您可以在o(n(：第一次进行 - 获取数组的所有元素(p(和第二次元素的产物 - 假设在开始时，左侧部分是一个，而第二是p，在每个步骤上，我在x [i]上乘以乘以x [i]右划分。继续过程，直到左侧小于右。

由于您有大量的数字，因此您需要一些数字乘法。因此，也许您最好转到[i]，la [i]的一系列对数并转向新标准。

编辑：

正如@ciapan所述，标准64位小数的精度不足以在此处进行日志操作(因为值可能最高为10^18(。

为了解决此问题，您应该首先将源数组的值拆分为对：

s[2*i]   = a[i].toDouble / (10.0^9)
s[2*i+1] = a[i]/s[2*i]  

阵列S比源数组A长两倍，但其值不超过10^9，因此可以安全地应用日志操作，然后为数组找到所需的SX并将其分配为2以获取x以获取数组a。

不需要超过的对数逻辑。