如何更高效地实现向量均衡的算法？

Question

给定一个包含 n 个整数元素的向量，如何设计更高效的算法以产生最小数量的转换步骤，使得向量的所有元素都相等，已知：

• 在单个步骤中，您最多可以将一个点从一个元素传输到其相邻元素（[0，3，0] -> [1，2，0] 可以，但不是 [0，3，0] -> [1，1，1]）。
• 在单个步骤中，一个元素可以接收两个点：一个来自左侧的相邻元素，另一个来自右侧的相邻元素（[3，0，3] -> [2，2，2]）。
• 第一个元素和最后一个元素分别只有一个相邻元素，即第二个元素和第 n-1 个元素。
• 任何一步中，元素不能为负数。

示例：

Given :
 0, 3, 0
Then 2 steps are required :
 1, 2, 0
 1, 1, 1

Given :
 3, 0, 3
Then 1 step is required :
 2, 2, 2

Given :
 4, 0, 0, 0, 4, 0, 0, 0
Then 3 steps are required :
 3, 1, 0, 0, 3, 1, 0, 0
 2, 1, 1, 0, 2, 1, 1, 0
 1, 1, 1; 1, 1, 1, 1, 1

我的当前算法基于元素两侧整数之和。但我不确定它是否会产生最小步骤。

顺便说一下，这个问题是一个代码竞赛的一部分（由Criteo创建 http://codeofduty.criteo.com），已经结束了。

- astony

---

@astony：在一个步骤中，您可以将至少一个点从元素转移到其邻居。 您是指 最多 吗？ - Mark Peters

听起来非常像“作业”。 - Orbling

当您可以将其归一化为1时。因为在每个步骤中，您只能转移一个元素。步骤数的下限是N-1。（这是将最大元素归一化所需的步骤数）。 - Ricky Bobby

@Orbling 不是作业，跟一个编程竞赛有关。已经结束了，我正在尝试找到更好的解决方案。我正在按照 @Mark 的建议草拟我的解决方案。但你说得对，听起来像 ;) - astony

@Orbling 我添加了上下文的提及，即代码竞赛。谢谢。 - astony

Answer 1

这里有一种方法。你知道数组的总和，所以你知道每个单元格中的目标数字。因此，你也知道每个子数组的目标总和。然后遍历数组，在每一步上做出一个决定：

1. 向左移动1：如果前一个元素的总和小于期望值。
2. 向右移动1：如果当前元素的总和大于期望值。
3. 什么都不做：如果上述两个条件都不满足。

重复以上步骤，直到不再进行更改（即对每个元素只应用3）。

    public static int F(int[] ar)
    {
        int iter = -1;
        bool finished = false;
        int total = ar.Sum();

        if (ar.Length == 0 || total % ar.Length != 0) return 0; //can't do it
        int target = total / ar.Length;

        int sum = 0;

        while (!finished)
        {
            iter++;
            finished = true;
            bool canMoveNext = true;

            //first element
            if (ar[0] > target)
            {
                finished = false;
                ar[0]--;
                ar[1]++;

                canMoveNext = ar[1] != 1;
            }

            sum = ar[0];
            for (int i = 1; i < ar.Length; i++)
            {
                if (!canMoveNext)
                {
                    canMoveNext = true;
                    sum += ar[i];
                    continue;
                }

                if (sum < i * target && ar[i] > 0)
                {
                    finished = false;
                    ar[i]--;
                    ar[i - 1]++;
                    sum++;
                }
                else if (sum + ar[i] > (i + 1) * target && ar[i] > 0) //this can't happen for the last element so we are safe
                {
                    finished = false;
                    ar[i]--;
                    ar[i + 1]++;

                    canMoveNext = ar[i + 1] != 1;
                }

                sum += ar[i];
            }
        }

        return iter;
    }

- Petar Ivanov

---

对于第三个例子，你的代码可能会给出正确的步骤数，但是中间步骤是无效的（与我的第三个约束条件相矛盾）：给定 [4,0,0,0,4,0,0,0]，需要3步 [3,0,0,1,3,0,0,1]，[2,0,1,1,2,0,1,1]，[1,1,1,1,1,1,1,1]。我会尝试自己修复它。不管怎样，谢谢。 - astony

嗯...不，是3，我刚刚运行了它：|4, 0, 0, 0, 4, 0, 0, 0|，|3, 1, 0, 0, 3, 1, 0, 0|，|2, 1, 1, 0, 2, 1, 1, 0|，|1, 1, 1, 1, 1, 1, 1, 1|。 - Petar Ivanov

恐怕你的算法对于第一个例子不起作用，它只给出了1步。 - B. Decoster

哈，搞定了！你忘记了“特殊情况”（即：你最多可以将一个点从元素转移到其邻居）。 - B. Decoster

不，我没有忘记。只需运行第一个示例-它将给出2。你们是如何得到不同的结果的？难道你们不只是复制粘贴代码吗？ - Petar Ivanov

Answer 2

我有一个想法。我不确定它是否能产生最优结果，但感觉它可以。

假设初始向量是大小为N的向量V。你需要两个额外的大小为N的向量：

• 在L向量中，从左边开始求和： L[n] = sum(i=0;i<=n) V[n]
• 在R向量中，从右边开始求和： R[n] = sum(i=n;i<N) V[n]

你最后需要一个特定的值：V的所有元素的总和应该等于k*N，其中k为整数。并且你有L[N-1] == R[0] == k*N

让我们看看L向量。对于任何n，想法是考虑将V向量分成两部分，一部分从0到n，另一部分包含其余部分。如果L[n]<n*k，那么你必须从第二部分中填充第一部分的值。如果L[n]>n*k，则反之。 如果L[i]==i*k，那么恭喜你，这个问题可以被分解为两个子问题！ 没有理由将第二个向量的任何值转移到第一个向量，反之亦然。

然后，算法很简单：对于每个n的值，检查L[n]-n*k和R[n]-(N-n)*k的值，并相应地采取行动。只有一个特殊情况，如果L[n]-n*k>0 并且 R[n]-(N-n)*k>0（V[n]的值很大），你必须在两个方向上都清空它。只需随机选择一个方向进行传输。

当然，不要忘记相应地更新L和R。

编辑：实际上，似乎只需要L向量。这是一个简化的算法。

• 如果L[n]==n*k，则不执行任何操作
• 如果L[n]<n*k，则将一个值从V[n+1]转移到V[n]（如果V[n+1]>0）
• 如果L[n]>n*k，则将一个值从V[n]转移到V[n+1]（如果V[n]>0）

如果你被要求从V[n]转移到V[n-1]和V[n+1]，只需随机转移一次，它不会改变最终结果。

- B. Decoster

Answer 3

感谢Sam Hocevar提供的以下替代实现方法，与fiver的实现方法相比：

public static int F(int[] ar)
{
    int total = ar.Sum();

    if (ar.Length == 0 || total % ar.Length != 0) return 0; //can't do it
    int target = total / ar.Length;

    int[] left = new int[ar.Length];
    int[] right = new int[ar.Length];
    int maxshifts = 0;
    int delta = 0;
    for (int i = 0; i < ar.Length; i++)
    {
        left[i] = delta < 0 ? -delta : 0;
        delta += ar[i] - target;
        right[i] = delta > 0 ? delta : 0;
        if (left[i] + right[i] > maxshifts) {
            maxshifts = left[i] + right[i];
        }    
    }

    for (int iter = 0; iter < maxshifts; iter++)
    {
        int lastleftadd = -1;

        for (int i = 0; i < ar.Length; i++)
        {
            if (left[i] != 0  && ar[i] != 0)
            {
                ar[i]--;
                ar[i - 1]++;
                left[i]--;
            }
            else if (right[i] != 0 && ar[i] != 0
                              && (ar[i] != 1 || lastleftadd != i))
            {
                ar[i]--;
                ar[i + 1]++;
                lastleftadd = i + 1;
                right[i]--;
            }
        }
    }

    return maxshifts;
}

- astony