查找使数组的所有元素等于0的最小移动次数

Question

1.索引x处元素可以在一次移动中直接移动到x+1，x+2位置或x-1，x-2位置，之后移动计数将增加。

例如,在数组中,最小移动将为31：

1. 索引4处的所有8个元素可以在总共16次移动中移动到索引0（因为所有8个元素都需要2次移动）。移动:16.
2. 索引5中的3个元素可以在3步中移动到索引3（3个元素每步移动1步），索引5中剩余的5个元素可以在10步中移动到索引2（5个元素每步移动2步，所以总共移动10步）。移动=16+3+10=29。
3. 索引6中的2个元素在2次移动中移动到索引7（每次移动1次）。移动=29+2=31。

下面是我的代码，但不在工作状态

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)，我们保持了一个大小为2的adverse数组，它保持了当我们将偶数和奇数索引从i位置移动到第(i+1)位置时移动元素的成本。我们从左到右迭代给定的数组，并计算将所有仍然留在左边的元素移到索引i的左边的代价。这样的成本可以使用开销数组来计算（参考下面的代码）。如果在任何一步，有可能用正整数抵消掉一些负整数，那么我们首先提取那些元素，如果在中和过程的下一步中，他从i移动到(i+1)，那么这些元素将花费我们+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)。