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

Question

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

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

Answer 1

可以从左向右扫描，将扫描到的最小整数移动到每次扫描到的整数之和为负时结束。证明我们的想法是，如果我们把贪婪算法和任何最优解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