algorithm - 均衡向量的更有效算法是什么？

Question

给定一个整数类型的 n 个元素的向量，什么是更有效的算法，它产生最少数量的转换步骤导致一个向量，它的所有元素都相等，知道:

• 在一个步骤中，您最多可以将一个点从元素转移到它的邻居([0, 3, 0] -> [1, 2, 0] 可以，但 [0, 3, 0] -> [1, 1, 1]).
• 在单个步骤中，一个元素可以获得 2 个点:一个来自其左侧邻居，一个来自右侧 ([3, 0 , 3] -> [2, 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 创建)的一部分。

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;
    }