1 #include
2 using namespace std;
3 /* Zlozonosc czasowa: O(n). */
4
5 const int MAX = 1000000;
6
7 int n;
8 int a[MAX];
9
10 void odczyt()
11 {
12 scanf(%dn, &n);
13 for (int i = 0; i < n; i++)
14 scanf(%d, &a[i]);
15 }
16
17 int main()
18 {
19 odczyt();
20 /* Znajdujemy kandydata na lidera. */
21 int lider = 0; /* jakakolwiek wartosc */
22 int ile = 0; /* liczba wystapien kandydata na lidera */
23 for (int k = 0; k < n; k++)
24 {
25 if (ile == 0)
26 {
27 /* na lidera ustawiamy pierwszy z brzegu element tablicy */
28 lider = a[k];
29 ile = 1;
30 }
31 else
32 if (lider == a[k])
33 /* odnotowujemy nowe wystapienie lidera */
34 ile++;
35 else
36 /* usuwamy dwa rozne elementy */
37 ile--;
38 }
39 /* Po czym sprawdzamy, czy rzeczywiscie jest on liderem. */
40 ile = 0;
41 for (int i = 0; i < n; i++)
42 if (a[i] == lider)
43 ile++;
44 if (ile > n / 2)
45 printf(%dn, lider);
46 else
47 printf(Nie ma lideran);
48 return 0;
49 }