algorithm - 最少的交易

我们得到n节点。他们每个人都有价值。有些小于0，有些大于。重要的是，所有这些值的和等于0。
现在，node numberi连接到nodei-1 mod n和i+1 mod n（因此node0连接到n和1）。
只有连接的节点才能在它们之间进行事务处理事务正在从一个节点发送一些值到另一个节点-它可以是我们希望的任何值，当然可以大于0我们需要将最小事务量计算为所有节点的偶数值-因此在事务之后，所有节点的值都将小于cc>。
有什么办法吗？

最佳答案

将MINCOST（i，r）设为将第一个i节点归零所需的最小事务数，将r（可能为负）总值发送到节点i的右侧。由于节点0到i-1中的总值必须归零，因此发送到右侧的总值还确定发送到左侧的总值我们将计算向右发送到节点i的成本，而不是向左发送到节点n-1的成本
我们寻找的答案是所有r的最小成本（n，r）。
当x=0时，设Z（x）=0，否则设1。
定义所有r的最小成本（0，r）=0
我们可以计算当我们将区域向右扩展一个节点时，成本如何变化：
设值[i]=x，则：
最小成本（i+1，r）=最小成本（i，r-x）+Z（r-x）
因此，有了以上这些，我们就可以很容易地提出一个o（n^2）动态规划算法，但是如果我们对mincost（i，？）的值使用正确的表示，我们实际上可以做o（n）
注意，当我们从i转换到i+1时，与成本相关的值会发生变化。我们只需要累积总的移位，而不是实际的移位。除某一特定价值的成本外，所有成本都会增加。我们可以把所有成本加起来，然后记下成本应该减少的单个值。
因此对于任何i，整个函数r->mincost（i，r）可以用成本递减值的bag（multiset）和总累积值和成本转移来表示，并且我们可以在每次i的增量中以恒定的时间更新它。
最后，只需找出减量最大的值，然后将减量的个数减去总累计成本移位，就可以找到整个数组归零的最佳成本。
代码实际上比解释短得多下面是一个python实现：

def minTransactions(nodeValues):
    shift=0
    decrements={0:0}
    for nodeValue in nodeValues:
        shift+=nodeValue
        decrements[-shift] = decrements.get(-shift,0)+1
    mostdecs=-1;
    for k in decrements.keys():
        if decrements[k] > mostdecs:
            mostdecs=decrements[k]

    return len(nodeValues)-mostdecs

您可以看到它在这里运行，扩展到实际打印事务：
https://ideone.com/gkJadt

关于algorithm - 最少的交易，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50061357/