dsal 分布的地雷的最高值和最小值之间的最小差异

分布的地雷的最高值和最小值之间的最小差异

原文： https://www.geeksforgeeks.org/minimum-difference-between-the-highest-and-the-smallest-value-of-mines-distributed/

给定 n 个公司和m个油矿具有价值，任务是公平地在n个公司之间分配这些矿山。那就是获得最高矿产价值的公司与获得最低矿产价值的公司之间的差异应该是最小的。计算最小差异。请注意，分配给每个公司的油矿应彼此相邻。另外， m >= n

示例：

输入：n = 2，m = 4 [地雷的 HTG2]值= [6、10、13、2] 输出：1 – >地雷分配为 {（6，10），（13，2）}，因此输出为（6 + 10）–（13 + 2）= 1

输入：n = 3，m = 4 地雷值= [6、10、13、2] 输出：9 – >地雷分布为 {（6），（10），（13，2）}，因此输出为（13 + 2）–（6）= 9

来源：三星 RnD 3 小时编码回合问题

方法：

构造一个数组，使每个索引处的值包含当前值与该数组中所有先前值的和。
在我们的解决方案数组中包括数组中的最后一个值。
通过从倒数第二个索引开始的给定 m-1 值中选择 n-1 值来递归构造所有可能的解决方案数组（因为数组中的最后一个值已包含在内）在我们的解决方案数组中）。
从解决方案数组中当前索引处的值中减去下一个索引处的值，以获取除最后一个值以外的每个索引处的值。计算所有解决方案数组的最大值和最小值之间的差，并返回最小值。

让我们以示例的方式逐步了解上述方法：

最初，提供的输入如下：

在步骤 1 之后，我们的数组如下所示：

在步骤 2 之后，解决方案数组如下所示：

在步骤 3 之后，我们得到以下可能的解决方案数组：

在步骤 4 之后，我们的解决方案数组看起来像下面给出的数组。然后，我们为所有数组计算数组中最大值和最小值之间的差，并返回最小值（在本例中为 9）。

下面是上述方法的实现：

# Python3 code to minimize the difference  
# between the highest and lowest value containing company 

# This function constructs the solution array  
# recursively and returns the difference  
# between the highest and lowest value. 
def func(solArr, arr, index, n): 

    # If the values have been distributed, 
    # compute the difference 
    if n == 0: 
        for i in range(len(solArr)-1): 
            solArr[i] = solArr[i] - solArr[i + 1] 

        return max(solArr) - min(solArr) 

    else: 

        # solArr can be constructed even if we  
        # don't include the current value 
        if index >= n: 
            return min(func(solArr[:] + [arr[index]], arr, index-1, n-1),  
                       func(solArr[:], arr, index-1, n)) 

        # solArr can't be constructed hence  
        # we have to include the current value     
        else: 
            return func(solArr[:] + [arr[index]], arr, index-1, n-1) 

n = 3
arr = [6, 10, 13, 2] 

# Construct array such that value at each index  
# contains the sum of current and all previous  
# values in the array. 
for i in range(1, len(arr)): 
    arr[i] += arr[i-1] 

# Include the last value of  
# the array in our solution array. 
solArr = [arr[-1]] 

print(func(solArr[:], arr, len(arr)-2, n-1))

Output:

时间复杂度： $O((n-1) * {m-1\choose n-1})$