algorithm - 使所有前缀总和 >=0 所需的最小重新分配

Question

给出一个整数数组，例如： 10, -10, -1, -1, 10 。我必须找到最小的重新分配，使得数组的所有前缀总和> = 0。假定数组中所有元素的总和
为非负数。在上面的示例中，我们可以将 -10 移动到数组的末尾以使所有前缀和为正。不知道如何有效地解决这个问题。取一个数字并将其插入其他任何地方将被视为一次重新分配。该问题将通过另一种类型的重新分配来解决：

1. 任何负数都可以移动到数组的末尾

Answer 1

我们可以从左到右扫描，每次扫描的整数之和为负时，将扫描到的最小整数移动到最后。证明的想法是，如果我们将这个贪心算法所做的与任何最优解 OPT 进行比较，只要贪心算法和 OPT 移动了相同数量的整数，贪心算法的总移动量小于或等于（即，更大，因为我们正在移动负数）而不是 OPT，因此贪婪永远不会采取任何行动使其落后于 OPT。

import heapq


def min_relocations(lst):
    relocations = 0
    heap = []
    total = 0
    for x in lst:
        heapq.heappush(heap, x)
        total += x
        if total < 0:
            relocations += 1
            total -= heapq.heappop(heap)
    return relocations