Каков более эффективный алгоритм для выравнивания вектора?

Для вектора из n элементов типа integer наиболее эффективный алгоритм, который дает минимальное число шагов преобразования, приводящее к вектору, у которого все его элементы равны, зная, что:

  • за один шаг вы можете перенести не более одной точки от элемента к ее соседям ([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

Мой текущий алгоритм основан на суммах целых чисел по каждой стороне элемента. Но я не уверен, что это приведет к минимальным шагам.

FYI проблема является частью конкурса кода (созданного Criteo http://codeofduty.criteo.com), который закончился.

Ответы

Ответ 1

Вот путь. Вы знаете сумму массива, поэтому вы знаете номер цели в каждой ячейке. Таким образом, вы также знаете целевую сумму для каждого подмассива. Затем итерации по массиву и на каждом шаге вы делаете предчувствие:

  • Переместить 1 влево: если сумма до предыдущего элемента меньше желаемого.
  • Переместить 1 вправо: если сумма до текущего элемента более чем желательна
  • Не делайте ничего: если оба из них являются ложными

Повторяйте это, пока не будет сделано никаких изменений (т.е. вы применили только 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;
    }

Ответ 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], просто перетащите случайным образом один раз, это не изменит окончательный результат.

Ответ 3

Благодаря Сэму Хочевару, для следующей альтернативной реализации пятой:

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