均衡圆形阵列

Question

首先,这不是一个家庭作业问题,这是一个面试问题(阿里巴巴).

最初的问题是"在仓库之间运输货物以使所有仓库具有相同的库存,所有这些仓库构成一个圆圈."

我把问题抽象如下:

有一个圆形整数数组,现在你需要均衡圆形数组(即,你需要使圆形数组中的每个元素具有相同的值).所以你必须从一个元素"移动一些价值"到另一个元素.

例如,有一个圆形数组:

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,您就可以得到最小成本流问题.

您可以在此页面找到几种解决方法:"最低成本流,第2部分:算法".