时间戳

首页 > 解决方案 > 找到使数组的所有元素都等于 0 的最小移动次数

algorithm - 找到使数组的所有元素都等于 0 的最小移动次数

问题描述

我有一个数组 A = {-8,-5,0,-3,8,8,2,-2} ，我想计算最小移动次数需要仅使用数组元素来制作数组 0 的所有元素，给定以下条件-->

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

  1. 在数组的开始索引（即 0）之前和结束索引（即数组的长度）之后，不能移动任何元素。

例如，在最小移动以上的数组中将是 31：

  1. 索引 4 处的所有 8 个元素都可以移动到索引 0，总共 16 次移动（因为所有 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。

再举一个输入数组 {-1,-1,0,1,1} 的例子，最佳解决方案给出答案 3 如下--> 1 从索引 3 移动到索引 1 在 1 移动，然后 1 从索引 4 移动到索引0 在 2 动作中，所以总动作将是 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;
}

标签： algorithmdata-structures

解决方案

给定的问题需要建设性的解决方案。由于移动的跨度延伸到(x - 2, x + 2)，我们维护一个大小为 2 的数组，当我们从偶数和奇数索引从i移动到第 ( i + 1)overhead位置时，它维持移动元素的成本. 我们从左到右遍历给定的数组，并计算将所有仍然在左边的元素移动到索引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)。

推荐阅读