通过添加元素来减少数组

Question

我在测试中遇到了这个问题.

给定一个数组,以最小的成本将数组减少为单个元素.要减少,请从数组中删除两个元素,添加这两个数字并将总和保留在数组中.每个操作的成本是该步骤中删除的元素的总和.

例如,让数组 A = [1,2,3]

然后,我们可以删除1和2,添加它们并将总和保留在数组中.该步骤的成本为(1 + 2)= 3.

所以A = [3,3],成本= 3

在第二步中,我们可以从数组中删除这两个元素,并将总和再次保留在数组中.这一步的成本是3 + 3 = 6.

所以,A = [6],成本= 6

因此总成本为9(6 + 3).

我尝试对数组进行排序,并将元素从递减添加到增加,但如果存在重复元素则会失败.

我的算法的伪代码

sort(Array)
cost = 0
for(i=0; i<Array.length - 1; i++) {
   Array[i+1] = Array[i] + Array[i+1]
   cost = cost + Array[i+1]
}

上面提到的算法不起作用.我想出了一个可能会失败的案例.如果Array = [5,5,5,5],则Cost = 45,根据上述算法.

但是,如果我们将前两个元素和最后两个元素相加,然后将剩余的两个元素相加,则总成本为40.(第一步,成本= 10*2,下一步另外20)

什么是一个有效的算法呢？

Answer 1

您在正确的轨道上排序数组并首先汇总最低元素.问题是:两个最低元素的总和可能大于那个之后的下一个元素,所以你不能把它放在前面.但它也可以比最后一个元素小,所以你也不能把它放在后面.您必须将总和放入它所属的地方并进行排序.

示例:如果您的列表是[1, 1, 3, 3],那么1+1应该放在前面,即[2, 3, 3],如果我们有[2, 2, 3, 3],那么总和2+2必须放在后面[3, 3, 4],而且[2, 2, 3, 5]必须放在中间位置,即[3, 4, 5].

一种简单的方法是使用堆结构.这些在大多数语言中都可用,并提供了获取和删除最小元素以及在正确位置插入元素的方法.这是Python中的一个例子:

import heapq
def reduce_sum(lst):
    heapq.heapify(lst)
    s = 0
    while len(lst) > 1:
        first = heapq.heappop(lst)
        second = heapq.heappop(lst)
        s += first + second
        heapq.heappush(lst, first + second)
    return s

reduce_sum([1,2,3])      # 9
reduce_sum([5, 5, 5, 5]) # 40

如果你不能使用堆,你仍然可以迭代数组以找到放置求和元素的正确位置,或者使用二进制搜索来更快地完成.