Условие
В командных олимпиадах по программированию для решения предлагается не больше 11 задач. Команда может решать предложенные задачи в любом порядке. Подготовленные решения команда посылает в единую проверяющую систему сорвенований. Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет статистически обрабатывать пришедшие запросы, чтобы определить наиболее популярные задачи. Следует учитывать, что количество запростов в списке может быть очень велико, так как многие соревнования проходят с использованием Интернет.
Перед текстом программы кратко опишите используемый вами алгоритм решения задачи.
На вход программе в первой строке подаётся количество пришедших запросов N. В каждой из последующих N строк записано название задачи в виде текстовой строки. Длина строки не превосходит 100 символов, название может содержать буквы, цифры, пробелы и знаки препинания.
Пример входных данных:
6
А+В
Крестики-Нолики
Прямоугольник
Простой делитель
А+В
Простой делитель
Программа должна вывести список из трёх наиболее популярных задач с указанием количества запросов по ним. Если в запросах упоминаются менее трёх задач, то выведите информацию об имеющихся задачах. Если несколько задач имеют ту же частоту встречаемости, что и третья по частоте встречаемости задача, их тоже нужно вывести.
Пример выходных данных для приведённого выше примера входных данных:
А+В 2
Простой делитель 2
Крестики-Нолики 1
Прямоугольник 1
Моё решение
#include <iostream> #include <string.h> #include <stdio.h> struct info { int count; std::string name; }; int main() { int N; scanf("%d%*c", &N); info arr[11]; std::string bufer; int found = 0, arr_count = 0; for (int i = 0; i < N; i++) { std::getline(std::cin, bufer); for (int j = 0; j < N; j++) { if (arr[j].name == bufer) { arr[j].count++; found = 1; break; } } if (found == 0) { arr[i].name = bufer; arr[i].count = 1; arr_count++; } found = 0; } for (int i = 0; i < arr_count; i++) { for (int j = 0; j < arr_count-1; j++) { if (arr[j].count < arr[j+1].count) { std::swap(arr[j], arr[j+1]); } } } for (int i = 0; i < arr_count; i++) { std::cout << arr[i].name << " " << arr[i].count << std::endl; if (i == 2) { while (arr[2].count == arr[++i].count) { std::cout << arr[i].name << " " << arr[i].count << std::endl; } break; } } return 0; }