什么是更有效的算法来均衡矢量？

Question

给定n个整数类型元素的向量,产生最小数量的变换步骤的效率更高的算法是什么,导致所有元素等于的向量,知道:

• 在一个步骤中,你可以从元素到其邻居最多转移一个点([0,3,0] - > [1,2,0]是好的但不是[0,3,0] - > [1, 1,1].
• 在一个步骤中,一个元素可以接收2个点:一个来自其左邻居,一个来自右边([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创建)的一部分已经结束.

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