Question

Cerința

Se dă un vector cu n elemente, numere naturale. Verificați dacă vectorul are un element majoritar. Numim element majoritar o valoare pentru care numărul de apariții în vector este mai mare decât n/2.


Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, reprezentând elementele vectorului.


Date de ieșire

Programul va afișa pe ecran mesajul NU, dacă vectorul nu are un element majoritar, respectiv DA X, dacă vectorul are un element majoritar, unde X este valoarea acestuia.


Restricții și precizări

1 ≤ n ≤ 100.000

cele n numere citite vor fi mai mici decât 1.000.000.000

Aceasta este solutia mea si imi da 70 de puncte,din cauza limitari de timp

#include


using namespace std;


int main()

{

int n,X,nr,ok=1;

cin>>n;

int v[n];

for(int i=1;i<=n;i++)

cin>>v[i];

for(int i=1;i<=n;i++)

{nr=1;

for(int j=1;j<=n;j++)

if(v[i]==v[j])nr++;

if(nr>n/2){X=v[i];i+=n;ok=0;}

}

if(ok==1)cout<<"NU";

else cout<<"DA "<}

Answer 1

Răspuns:

#include <iostream>

using namespace std;

int v[100001], n, i, x = 0, nrmax = 0, xg = 0;

bool arg;

void quicksort(int low, int high)

{

int x, i, j, t;

i = low;

j = high;

x = v[(i + j) / 2];

do {

 while ((i < high) && (v[i] < x)) i++;

 while ((j > low) && (v[j] > x)) j--;

 if (i <= j) {

  t = v[i];

  v[i] = v[j];

  v[j] = t;

  i++;

  j--;

 }

} while (i <= j);

if (low < j) quicksort(low, j);

if (i < high) quicksort(i, high);

}

int main()

{

cin >> n;

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

 cin >> v[i];

quicksort(0, n - 1);

nrmax = 1;

x = v[0];

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

{

 if (v[i] == x)

  nrmax++;

 else

 {

  nrmax = 1;

  x = v[i];

 }

 if (nrmax > n / 2)

  xg = x;

}

 

if (xg)

 cout << "DA " << xg;

else

 cout << "NU";

}

Explicație:

Astept intrebari. 100p pe pbinfo.