найти минимальное количество ходов, чтобы все элементы массива были равны 0

Question

У меня есть массив A = {-8, -5,0, -3,8,8,2, -2}, я хочу вычислить минимальное количество ходов, необходимых для создания всех элементов массива 0 с использованием элементов массиватолько при условии соблюдения следующего условия ->

1.an элемент с индексом x может быть перемещен непосредственно в положение x + 1, x + 2 или в положение x-1, x-2 за один ход,после этого количество ходов увеличится.

ни один элемент не может быть перемещен до начального индекса массива, т. Е. 0 и после конечного индекса, т. Е. Длины массива.

например, в массиве выше минимального перемещения будет 31:

1. все 8 элементов в индексе 4 могут быть перемещены в индекс 0 в общей сложности 16 ходов (поскольку все 8 элементов требуют 2 хода).ходы: 16.
2. 3 элемента из индекса 5 можно переместить в индекс 3 за 3 хода (3 элемента занимают по 1 ходу каждый), а оставшиеся 5 элементов из индекса 5 можно переместить в индекс 2 за 10 ходов (5элементы требуют 2 хода каждый, итого 10 ходов).ходы = 16 + 3 + 10 = 29.
3. 2 элемента из индекса 6 перемещаются в индекс 7 за 2 хода (по 1 ходу каждый).move = 29 + 2 = 31.

возьмите другой пример для входного массива {-1, -1,0,1,1}, оптимальное решение дает ответ 3 следующим образом -> 1 из индекса3 шага к индексу 1 на 1 ходу, затем 1 к индексу 4 на 2 шага к индексу 0, поэтому общее количество ходов будет 3.

Я пытался написать код на c ++, но Динт получил оптимальное решение, также не смогчтобы охватить все сценарии.

ниже мой код, но не в рабочем состоянии

int solution1(vector < int > & c) {

  int alen = c.size();
  if (alen == 0) return -1;

  int move = 0;
  int moved = 0;
  for (int j = 0; j < alen; ++j) {
    if (c[j] < 0) {
      for (int k = j + 1; k < alen; ++k) {
        moved = 0;
        if (c[k] > 0) {
          c[j] = 0 - c[j];
          if (c[j] <= c[k]) {
            c[k] = c[k] - c[j];
            moved = c[j];
            c[j] = 0;
          } else {
            c[j] = c[k] - c[j];
            moved = c[k];
            c[k] = 0;
          }
          if (k - j >= 2) {
            if ((k - j) % 2)
              move += ((k - j + 1) / 2) * moved;
            else
              move += ((k - j) / 2) * moved;
          } else {
            move += moved;
          }
          if (c[j] == 0) break;
        }
      }
    } else if (c[j] > 0) {
      for (int kk = j + 1; kk < alen; ++kk) {
        moved = 0;
        if (c[kk] < 0) {
          c[kk] = 0 - c[kk];
          if (c[j] <= c[kk]) {
            c[kk] = c[j] - c[kk];
            moved = c[j];
            c[j] = 0;
          } else {
            c[j] = c[j] - c[kk];
            moved = c[kk];
            c[kk] = 0;
          }
          if (kk - j >= 2) {
            move += ((kk - j) / 2) * moved;
          } else {
            move += moved;
          }
          if (c[j] == 0) break;

        }
      }
    }

  }
  if (move > 0) return move;
  else return -1;
}

Answer 1

Данная проблема требует конструктивного решения.Поскольку диапазон перемещения распространяется на (x - 2, x + 2) , мы поддерживаем массив overhead размера 2, который сохраняет стоимость движущихся элементов при переходе от i до (i + 1) ^th позиция для четных и нечетных индексов.Мы перебираем данный массив слева направо и вычисляем стоимость перемещения всех оставшихся элементов слева от индекса i .Такая стоимость может быть рассчитана с использованием массива накладных расходов (см. Код ниже).Если на каком-либо шаге существует возможность отменить некоторые отрицательные целые числа с положительными целыми, мы сначала подберем те элементы, которые нам обойдутся в +1, если он перешел с i на (i+ 1) в нашем следующем шаге для процесса нейтрализации.

Смысл наблюдения в том, что если мы будем продолжать перемещать элемент с индексом x слева направо, то это 'добавлю только к стоимости ходов в точках (x + 1), (x + 3), (x + 5), ... и так далее.Вот код запуска для того же: https://ideone.com/TFunNG

int solve(vector<int> v) {
    vector<int> overhead(2,0);
    int num_of_moves = 0, sum = 0;
    for(int i = 0; i < v.size(); i++) {
        num_of_moves += overhead[i % 2];
        int left = abs(v[i]);
        if((sum > 0 && v[i] < 0) || (sum < 0 && v[i] > 0)) {
            int used = min(abs(sum), abs(v[i]));
            int diff = min(overhead[(i + 1) % 2], used);
            overhead[(i + 1) % 2] -= diff;
            overhead[i % 2] -= min(overhead[i % 2], (used - diff));
            left -= used;
        }
        sum += v[i];
        overhead[(i + 1) % 2] += abs(left);
    }

    assert(sum == 0);
    return num_of_moves;
}

Общая сложность решения во время выполнения: O (n) .