2

首先，这不是作业问题，而是面试问题（阿里巴巴）。

最初的问题是“仓库之间的货物运输，使所有仓库的库存相同，所有这些仓库组成一个圆圈”。

我将问题抽象如下：

有一个循环整数数组，现在你需要对循环数组进行均衡（即你需要使循环数组中的每个元素都具有相同的值）。所以你必须从一个元素“移动一些价值”到另一个元素。

例如，有一个循环数组：

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”。详细给出你的算法（只解释你的算法，不需要编码）。

4

2 回答 2

5

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

您可以在此页面上找到解决该问题的几种算法：“最小成本流，第 2 部分：算法”。

于 2013-05-08T10:02:39.693 回答
0

我在昨天举行的 hackwithinfy 2020 第 1 轮中遇到了完全相同的问题，我能够成功提交该问题的解决方案并获得满分（75）分，虽然我没有带代码，但我会尝试解释该算法如果您遇到任何困难，我一定会提供帮助。

所以，基本上我们需要做的是均衡数组的所有元素，因此我们将找到将整个数组转换为所有不同元素的成本，并打印所有成本中的最小值作为我们的答案。

例如 1 1 2 3 如果这是我们的数组，我们将尝试找到将数组的所有元素替换为 1 的成本，然后将数组的所有元素转换为 2 的成本，类似于 3，然后我们将找到这些成本中的最小值。正如我们所见，将数组的所有元素转换为 1 成本最低。

现在为了实现这一点，我使用了一个整数映射和一个向量，即 map > map1。现在，在获取输入时，我将数组的所有元素映射到它们在数组中出现的向量，现在我发现相邻出现之间的差异还考虑了最后和第一个的 diff b/w（因为数组是循环的）并发现这些差异的最大值，然后如果差异是偶数，那么成本是差异/2，否则差异-1/2。在某些极端情况下，当一个元素只出现一次时，也可以通过取 (length - index - 1) & (index) 的最大值来轻松解决。

现在，所有这些成本中的最小值将为我们提供答案。

如果您有任何疑问，请在下面发表评论，我将通过更多示例更简要地向您解释。

于 2020-03-31T11:50:41.573 回答