9703. Биоразнообразие

У Алисии огромный сад, в котором обитает множество животных, о которых она действительно заботится. После прослушивания подкаста о биоразнообразии она очень обеспокоена балансом между видами в своем саду. Она хочет знать, есть ли вид, который может обойти других. Для этого она решает провести перепись всех животных в саду, записав виды каждого из них. Можете ли Вы помочь ей проверить, действительно ли животных одного вида строго больше, чем животных всех других видов вместе взятых?

Вход. Первая строка содержит количество животных n (1 ≤ n ≤ 2 * 10⁵);

Каждая из следующих n строк содержит вид животного в виде строки длины не более 20, содержащей только буквенно-цифровые ASCII символы.

Выход. Вывести строку, которая встречается количество раз, больше суммы других, если таковая имеется. Иначе вывести “NONE”.

Пример входа 1	Пример выхода 1
3 frog fish frog	frog
Пример входа 2	Пример выхода 2
4 cat mouse mouse cat	NONE

РЕШЕНИЕ

структуры данных - стек

Анализ алгоритма

В задаче следует найти мажорирующий элемент. То есть следует найти слово, которое встречается более чем раз, где n – заданное количество слов.

Реализация алгоритма

Объявим используемые данные. Виды животных храним в массиве строк v.

Стек моделируем двумя переменными:

· maj – мажорирующий элемент;

· cnt – сколько раз элемент maj находится в стеке;

vector<string> v;

string maj;

int cnt;

Читаем входные данные.

cin >> n;

v.resize(n);

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

cin >> v[i];

Изначально устанавливаем стек пустым.

maj = ""; cnt = 0;

Обрабатываем входные строки, моделируем работу стека.

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

{

Если стек пустой (cnt = 0), то кладем в него элемент v[i].

if (cnt == 0) { maj = v[i]; cnt++; }

Если текущий элемент v[i] совпадает с вершиной стека maj, то кладем v[i] в стек.

else if (v[i] == maj) cnt++;

Иначе извлекаем элемент из стека.

else cnt--;

}

В переменной cnt подсчитаем, сколько раз число maj встречается в массиве v.

cnt = 0;

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

if (v[i] == maj) cnt++;

Если cnt > , то мажоранта существует. Иначе нет (res присвоим “NONE”).

if (2 * cnt > n) res = maj; else res = "NONE";

Выводим ответ.

cout << res << endl;