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

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. Ничего не предпринимать: если оба вышеприведенных значения ложнысделаны (т.е. вы применили только 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;
       }
   

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

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