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

标签 algorithm prefix-sum

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

  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

关于algorithm - 使所有前缀和 >=0 所需的最小重新分配,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/69675180/

相关文章:

algorithm - 明星总是会返回成本最低的路径吗?

python - 不理解这个递归的python代码

c# - 尝试从子控件列表中有效地找到公共(public)父控件

algorithm - 包含点的树 - 需要改进

algorithm - 应该使用什么类型的遍历来找到二叉树的总和?

CUDA:atomicAdd 花费太多时间,序列化线程

performance - codility GenomicRangeQuery 算法速度比较 Java 与 Swift

algorithm - PRAM if-then-else CREW/EREW

algorithm - 计算前缀和的并行算法

algorithm - 动态前缀和