hopingsteam

Element majoritar - elmaj

Jan 14th, 2017
598
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Problema rezolvata pe Tutoriale-Pe.NET
  2. // Citeste toata explicatia aici: http://tutoriale-pe.net/ro/elementul-majoritar-elmaj/
  3.  
  4. #include    <iostream>
  5. #include    <fstream>
  6.  
  7. using namespace std;
  8.  
  9. ifstream fin("elmaj.in");
  10. ofstream fout("elmaj.out");
  11.  
  12. const int LIM = 1000005;
  13.  
  14. int N;
  15. int V[LIM];
  16.  
  17. void Read()
  18. {
  19.     fin >> N;
  20.  
  21.     // Citim vectorul normal
  22.     for(int i = 0; i < N; i++)
  23.         fin >> V[i];
  24.  
  25.     // Declaram variabilele descrise mai sus
  26.     int contor = 0, candidat = 0, aparitii = 0;
  27.  
  28.     // Parcurgem vectorul
  29.     for(int i = 0; i < N; i++)
  30.     {
  31.         // Atunci cand contorul este 0, alegem elementul curent ca fiind candidatul
  32.         // si setam contorul pe "1"
  33.         if(contor == 0)
  34.         {
  35.             candidat = V[i];
  36.             contor = 1;
  37.         }
  38.         else
  39.         {
  40.             // Daca avem deja contorul pornit, verificam elementul curent si adaugam +1
  41.             // daca este acelasi nr ca si candidatul, si scadem -1 in caz contrar
  42.             if(V[i] == candidat)
  43.                 contor += 1;
  44.             else
  45.                 contor -= 1;
  46.         }
  47.     }
  48.  
  49.     // Mai parcurgem o data vectorul pentru a numara de cate ori apare candidatul
  50.     for(int i = 0; i < N; i++)
  51.         if(V[i] == candidat)
  52.             aparitii += 1;
  53.  
  54.     // Tratam cazul in care nu avem element majoritar
  55.     if(aparitii < N / 2 + 1)
  56.         fout << "-1";
  57.     else
  58.         fout << candidat << " " << aparitii;
  59. }
  60.  
  61. int main()
  62. {
  63.     Read();
  64.     return 0;
  65. }
RAW Paste Data