步骤最少数量需要的所有二进制位变成一个状态

Question

有是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

Answer 1

如果我的问题理解正确，思想一点点的将说服你，即使是动态规划是没有必要的 - 该解决方案完全是微不足道的。

这是我理解的问题是：你将得到一个数组a [1]的形式S的一个.. [M] 0和1，并且您允许操作<子>ķ，其中S <子>ķ装置翻转N个元素一个[K]，A [K + 1]，...一个[K + N-1]。这仅对于1≤k≤M-N + 1，明确的定义。

通过执行这些操作小号<子>的串k ，要达到全0，或全1的任一状态。我们将分别解决两个，并采取较小的数字。因此，假设我们要让他们都为0（另一种情况下，全1，是对称的）。

在重要思想是你绝不会想执行任何供电S _ķ超过一次（做两次就相当于根本做），和该操作的顺序并不重要。所以，问题是唯一确定您执行操作的哪个子集，这是容易确定。看一个[1]。如果是0，那么你知道你将不会执行小号 ₁ 。否则，就知道必须执行小号<子> 1 （因为这是一个将翻转[1]的唯一操作），所以执行它 - 这将从[1]到切换所有的位[N ]。下面看一个[2]（此操作后）。取决于它是否是1或0，你知道你是否将执行小号<子> 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));
}

Answer 2

我编码了算法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，则它是不可能的。

请注意，我既没有编译或测试的代码，但它应该工作。