Question

Se consideră un șir binar a[1], a[2], …, a[n]. Asupra șirului se poate efectua operația swap(i, j) prin care se interschimbă valorile a[i] și a[j]. Cerința Să se determine numărul minim de operații swap care pot fi efectuate astfel încât toate valorile de 1 să apară pe poziții consecutive în șir. Date de intrare Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații reprezentând elementele șirului binar. Date de ieșire Programul va afișa pe ecran numărul minim de operații swap care pot fi efectuate astfel încât toate valorile de 1 să apară pe poziții consecutive în șir. Restricții și precizări 1 ≤ n ≤ 100 000 Exemplu Intrare 14 1 0 0 1 0 1 1 0 1 0 0 0 1 0 Ieșire 2 Explicație Se efectuează de exemplu swap(1,5) și swap(13, 8) și astfel șirul devine 0 0 0 1 1 1 1 1 1 0 0 0 0 0, deci valorile de 1 ocupă o zonă continuă. Nu există posibilitatea ca printr-o singură operație să se obțină o secvență continuă de valori de 1.

Answer 1

Răspuns:

Explicație:

#include <iostream>

#include <bitset>

#include <fstream>

using namespace std;

int b[100001];

int n, i, j, secv, secvmax, nr1, nrswap,bit, rep;

int main()

{

  cin >> n;

  for (i=0; i<n; ++i)

  {

      cin >> b[i];

      nr1+=b[i];

  }

  for (j=0; j<nr1; ++j) secv+=b[j];

  secvmax=secv;

  for (i=nr1; i<n; ++i)

  {

      secv=secv-b[i-nr1]+b[i];

      if (secv>secvmax) secvmax=secv;

  }

  nrswap=nr1-secvmax;

  cout << nrswap;

}