arrays - 均衡圆形阵列

Question

首先，这不是作业题，是面试题(阿里巴巴)。

原问题是“仓库间运输 cargo ，使所有仓库库存相同，所有仓库围成一个圆圈。”

我将问题抽象如下:

有一个循环整数数组，现在需要对循环数组进行均等化(即需要使循环数组中的每个元素都具有相同的值) .因此，您必须将一些值从一个元素“转移”到另一个元素。

比如有一个圆形数组:

c_array = {1, 2, 3}, c_array[0] == 1, c_array[1] == 2, c_array[2] == 3。

要均衡圆形阵列，您必须将1从c_array[2]“移动”到c_array[0]。

有一些规则:

1. 移动必须在相邻元素之间；
2. 移动量必须是整数；
3. 将 k 从一个元素移动到另一个元素需要 k；

另一个例子:

c_array = {1, 2, 7, 6}，c_array[0] == 1，c_array[1] == 2 >，c_array[2] == 7，c_array[3] == 6。

解决方法是:

将2从c_array[3]移动到c_array[0]，花费2；

将3从c_array[2]移动到c_array[1]，花费3；

将1从c_array[1]移动到c_array[0]，花费1；

总成本是 6。

问题是找到一个成本最低的解决方案。如果没有有效的解决方案，输出“NO”。详细给出你的算法(只解释你的算法，不需要代码)。

Answer 1

如果将圆形数组转换为图形，其中每个节点对应于某个数组元素，节点的供需等于元素值与平均值之间的差值，每个节点通过边连接到它的两个邻居，边容量是无限的，每条边的成本是 1，你正好得到最小成本流问题。

您可以在此页面上找到解决该问题的几种算法:"Minimum Cost Flow, Part 2: Algorithms" .