给出一个整数数组,例如: 10, -10, -1, -1, 10 。我必须找到最小重新分配,使得数组的所有前缀和 >=0。数组中所有元素的总和
假设为非负数。在上面的例子中,我们可以将-10移动到数组的末尾,以使所有前缀和为正。不知道如何有效地解决这个问题。取出一个数字并将其插入到其他地方将被视为一次重新分配。
该问题需要通过另一种类型的重新分配来解决:
- 任何负数都可以移动到数组末尾
我们可以从左到右扫描,将迄今为止扫描的最小整数移动到
每次扫描的整数之和变为负数时结束。证据
想法是,如果我们将这个贪婪算法与任何算法进行比较
最优解 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
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)