以最小差异对阵列进行分区 [英] Partition the array with minimal difference

问题描述

给出N个整数的数组A.我需要找到X，以使以下两个值(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的值多个，则打印最小的值. /p>

约束:-

• 1< = N< = 10 ^ 5

• 1< = A[i]< = 10 ^ 18.

我找不到有效解决此问题的方法. 解决该问题的最佳方法应该是什么.有什么特殊的算法可以将大量的数字相乘.

解决方案

您可以在O(n)中执行此操作:第一个步骤-获取数组(P)的所有元素的乘积，第二个步骤-假设在开始时左边的部分是一个，第二个部分是P，在每一步上，i在X [i]上向左相乘，在X [i]上向右相除.继续该过程，直到左小于右.

由于您有大量数字，因此需要一些大数乘法.因此，也许您最好移至A [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]  

Array s是源数组a的两倍，但其值不超过10 ^ 9，因此可以安全地执行日志操作，然后为array s找到所需的sX并将其除以2以得到数组a的X .

不需要超精确的对数逻辑.

Given an array A of N integers . I need to find X such that the difference between the following 2 values (A[1] * A[2] * ... * A[X]) and (A[X+1] * A[X+2] * ... * A[N]) is minimum possible i.e. I need to minimize | (A[1] * A[2] * ... * A[X]) - (A[X+1] * A[X+2] * ... * A[N]) | and if there are multiple such values of X, print the smallest one.

Constraints:-

• 1 <= N <= 10^5

• 1 <= A[i] <= 10^18.

I am not able to find the approach to solve this problem in efficient way. What should be the best approach to solve this problem. Is there any special algorithm for multiplying large quantity of numbers.

解决方案

You can do it in O(n): first go - get the product of all elements of array (P) and the second go - assuming at start the left part is one and the second is P, on each step i multiply left on X[i] and divide right on X[i]. Continue the process until left is less than right.

Since you have large array of numbers, you need some big-number multiplication. So, maybe you better move to array of logarithms of A[i], LA[i] and move to new criteria.

Edit:

As mentioned by @CiaPan, the precision of standard 64-bit decimal is not enough for making log operation here (since values may be up to 10^18).

So to solve this problem you should first split values of the source array to pairs such that:

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

Array s is twice longer than source array a, but its values do not exceed 10^9, so it is safe to apply log operation, then find desired sX for array s and divide it to 2 to get X for array a.

Extra-precision logarithm logic is not required.

这篇关于以最小差异对阵列进行分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！