6

有一个由 M 个二进制数组成的数组，每个二进制数都处于状态“0”或“1”。您可以执行几个步骤来更改数字的状态，并且在每个步骤中，您都可以更改恰好 N 个连续数字的状态。当然，给定数字 M、N 和包含成员的数组，您将要计算将所有二进制数转换为一种状态（1 或 0）所需的最小步骤数。

如果 M = 6 且 N = 3 且数组为 1 0 0 1 0 0，则解将为 2。 说明：我们可以分两步翻转它们，使它们都为 1：我们从索引 2 翻转到 4，然后我们将数组转换为 111000，然后将最后三个 (N) 0 翻转为 1。

4

2 回答 2

6

如果我正确理解了这个问题，稍微思考一下就会让你相信，即使是动态编程也没有必要——解决方案完全是微不足道的。

这是我理解的问题：给你一个 0 和 1 的数组 a[1]..a[M]，你可以进行 S k形式的操作，其中 S k表示翻转 N 个元素 a [k],a[k+1],...a[k+N-1]。显然，这仅针对 1≤k≤M-N+1 定义。

通过执行一系列这些操作 S k，您希望达到全 0 或全 1 的状态。我们将分别解决这两个问题，并取较小的数字。所以假设我们想让它们全为 0（另一种情况，全为 1，是对称的）。

关键的想法是你永远不想执行任何操作 S k超过一次（执行两次等同于根本不执行），并且操作的顺序无关紧要。所以问题只是确定您执行的操作的哪个子集，这很容易确定。看[1]。如果它是 0，那么你知道你不会执行 S 1。否则，你知道你必须执行 S 1（因为这是唯一会翻转 a[1] 的操作），所以执行它 - 这会将所有位从 a[1] 切换到 a[N]。现在看 a[2]（在这个操作之后）。看是1还是0，就知道会不会执行S 2或不。依此类推——您可以确定在线性时间内执行多少操作（以及执行哪些操作）。

编辑：用 C++ 代码替换伪代码，因为有一个 C++ 标签。对不起丑陋的代码；当处于“比赛模式”时，我会恢复比赛习惯。:-)

#include <iostream>
using namespace std;
const int INF = 20000000;
#define FOR(i,n) for(int i=0,_n=n; i<_n; ++i)

int flips(int a[], int M, int N, int want) {
  int s[M]; FOR(i,M) s[i] = 0;
  int sum=0, ans=0;
  FOR(i,M) {
    s[i] = (a[i]+sum)%2 != want;
    sum += s[i] - (i>=N-1?s[i-N+1]:0);
    ans += s[i];
    if(i>M-N and s[i]!=0) return INF;
  }
  return ans;
}

int main() {
  int M = 6, N = 3;
  int a[] = {1, 0, 0, 1, 0, 0};
  printf("Need %d flips to 0 and and %d flips to 1\n",
         flips(a, M, N, 0), flips(a, M, N, 1));
}
于 2010-02-25T22:22:07.437 回答
3

我编写了 ShreevatsaR 提出的算法，但增加了队列改进以使其达到 M 中的真正线性时间。

int solve(vector<bool> bits, int N)
{
  queue<int> flips;
  int moves = 0;

  for (int i = 0; i < bits.size(); ++i)
  {
    if (!flips.empty() && flips.front() <= i - N)
      flips.pop();

    if ((bits[i] ^ (flips.size() % 2 == 0)) == 1)
    {
      if (i > bits.size() - N)
        return -1; // IMPOSSIBLE

      moves++;
      flips.push(i);
    } 
  }

  return moves;
}

只需在原件和倒置原件上运行它并取最小值（如果它们不是-1）。如果两者都是-1，那么这是不可能的。

请注意，我既没有编译也没有测试过该代码，但它应该可以工作。

于 2010-02-25T23:07:47.327 回答