使列表中每个位置的硬币数量相等所需的最小硬币移动次数

Question

给出了一个大小为n的数组coin，其中coin[i]表示位置i处的硬币数量。“移动”包括将一定数量的硬币从位置i移动到位置i+1或i-1。重新分配硬币所需的最小移动次数是多少，这样每个位置上正好有一枚硬币？你被保证有相同数量的硬币与有的插槽，以分配他们。

例如，给定输入

 [3, 0, 0, 0, 3, 0, 1]

输出为

[1, 1, 1, 1, 1, 1, 1]

null

解决这个问题的有效方法是什么？

Answer 1

你只需扫描内部边框，并计算需要转移的边框。这个计数是移动的最小数目。

找到这个最小值的Python代码：

def nb_moves(game):
    N=len(game)-1 # number of inside borders.
    sum = -1
    for i in range(N):
        sum += game[i]
        if i == sum : N -= 1 # no transfer needed between cells i and i+1 . 
    return N

实际上，让n是这个计数。n显然是移动次数的最小值。此外，可以达到这一最低限度：

如果有必须两边清空的单元格，则首先这样做：两个边框分两步处理，将块切割成两个平衡的块，并将一个单元格设置为1。

剩下的块是单调的，可以从左到右或者从右到左求解。

这样，每个内部边界只跨越一次，而且只能跨越一次。

In [275]: solve([3, 0, 0, 0, 3, 0, 1])
Out[275]: 4

In [276]: solve([2,2,0,0])
Out[276]: 3

In [277]: solve([1,2,0,1])
Out[277]: 1