Minimale Anzahl von Schritten erforderlich, um alle binären bits zu einem Staat

Question

Es gibt eine Reihe von M mit binären zahlen und jeder von Ihnen ist im Zustand '0' oder '1'.Sie können mehrere Schritte durchführen, in dem ändern des Status der zahlen und in jedem Schritt dürfen Sie zu ändern, den Zustand genau N fortlaufende Nummern.Angesichts der zahlen M, N und das array mit den Mitgliedern natürlich, Sie sind über die zur Berechnung der minimalen Anzahl von Schritten erforderlich, um die binären zahlen in einem Staat, also 1 oder 0.

---

Wenn M = 6 und N = 3, und das array ist 1 0 0 1 0 0, dann wird die Lösung 2.Erklärung:Wir können flip Sie, damit Sie alle 1 in zwei Schritten:wir blätterten von index 2 bis 4 und verwandeln wir das array 111000, und dann drehen die letzten drei (N) 0s 1.

Answer 1

Wenn ich die Frage richtig verstanden habe, ein wenig Gedanken werden Sie davon überzeugen, dass auch dynamische Programmierung ist nicht notwendig -. Die Lösung ganz trivial ist

Das ist die Frage, wie ich es verstehe: ein Array a gegeben ist [1] .. a [M] von 0 und 1, und Sie dürfen Operationen der Form S _k , wobei S _k Mittel, um die N Elemente a [k] kippen, a [k + 1], ... a [k + N-1]. Dies ist nur definiert für 1≤k≤M-N + 1, deutlich.

Durch eine Folge dieser Operationen S _{Ausführen k} , möchten Sie entweder den Status aller 0s oder alle 1s erreichen. Wir werden für beide lösen getrennt, und nehmen Sie die kleinere Zahl. Also nehmen wir sie alle 0 machen wollen (die anderen Fall alle 1s, ist symmetrisch).

Die entscheidende Idee ist, dass Sie würde nie eine Operation S _k ausführen wollen mehr als einmal (es zweimal tun, ist äquivalent zu tun es nicht), und dass die Reihenfolge der Operationen keine Rolle spielt. Also die Frage ist nur, um zu bestimmen, welche Teilmenge der Operationen, die Sie ausführen, und dies ist leicht zu bestimmen. Schauen Sie sich ein [1]. Wenn es 0 ist, dann wissen Sie, Sie werden nicht S ausführen ₁ . Else, wissen Sie, Sie S ₁ durchführen müssen (da dies die einzige Operation, die ein [1] wird Flip), es so durchführen - dies schaltet alle Bits von a [1] bis a [N ]. Nun ein Blick auf ein [2] (nach dieser Operation). Je nachdem, ob es 1 oder 0 ist, wissen Sie, ob Sie S durchführen wird ₂ oder nicht. Und so weiter -. Sie können bestimmen, wie viele Operationen (und welche) durchzuführen, in linearer Zeit

Edit: ersetzt Pseudo-Code mit C ++ Code, da es ein C ++ Tag. Sorry für den hässlichen Code; wenn in „Wettbewerb-Modus“ Ich Wettbewerb Gewohnheiten zurück. : -)

#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

Ich codierte bis der Algorithmus, ShreevatsaR vorgeschlagen, aber mit dem zusätzlichen queue Verbesserung um es zu realen linearen Zeit, in 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;
}

Nur ausführen, die auf das ursprüngliche und das invertierte original und nehmen Sie die minimale (wenn Sie sind nicht -1).Wenn es -1 ist, dann ist es unmöglich.

Beachten Sie, dass ich weder kompiliert oder getestet, dass code, aber es sollte funktionieren.