LIDER c++

[alfonsue]

Sędzia wywala mi błędną odpowiedź. Co moge poprawic ?

Ideone.com

#include
#include
#include<math.h>
using namespace std;
int main()
{

int ile, n, *tab, kand, t;
cin >> t;
while(t--){

    cin >> n;
    int *tab = new int [n];

    for(int i=0; i<n; i++)
        cin>>tab[i];

    kand = tab[0];
    ile = 0;
    for(int i = 1; i < n; i++)
    {
        if(tab[i] == kand)
        {
            ile += 1;
        }
        else
            if(ile > 0)
                ile -= 1;
            else
                kand = tab[i];
                ile = 1;
    }
    ile = 0;
    for(int i = 0; i < n; i++){
        if(tab[i] == kand){
            ile += 1;
        }
        else
            continue;
    }
    if(ile >= floor(n/2) + 1)
        cout << kand << endl;
    else
        cout << -1 << endl;
}
return 0;

}

[pawoj20]

1. Na poczatek sprawdz zakres elementu ai, bo w programie wydaje sie zle dobrany.
2. nie za bardzo rozumiem co robia petle sprawdzajace operujace na zmiennych kandydat ile, ale moze maja jakis sens.
3. Podejrzewam ze jest jakas pomylka w ponizszym fragmencie:

else
                kand = tab[i];
                ile = 1;

Moze to brak klamer albo nieodpowiednie wciecie.

[narbej]

Dokładnie tak jak pisze @pawoj20,
Ad 1 "… .liczb ai (0 ≤ ai ≤ 10^18)."
AD 2 Tak działa algorytm wyszukiwania lidera i jest prawie ok
AD 3 tak tu zabrakło nawiasów, chociaż w innym jest ich nadmiar np:
zamiast:

 for(int i = 0; i < n; i++){
        if(tab[i] == kand){
            ile += 1;
        }
        else
            continue;
    }

spokojnie można:

 for (int i = 0; i < n; i++)
        if (tab[i] == kand)
            ++ile;

AD AD2
Np dla takiego testu:
1
5
1
1
2
2
1
dostałbyś WA, ale na twoje szczęście takiego testu chyba nie ma na spoju więc ten błąd nie wpłynie na wynik.

---

=====

---

Danych do wczytania jest sporo, więc potem [po poprawkach] dostaniesz tle. Musisz wyłączyć synchronizację ios::sync_with_stdio(0); Kilka innych mało istotnych szczegułów:
<cmath> a nie <math.h>
Wystarczy ile > n/2, ale jeśli się boisz dzielić, to możesz 2*ile > n
Jeżeli wcześniej masz int *tab to potem można już tab = new ....
gdzie int oczywiście trzeba “troszkę” zwiększyć