Задача №5. Призёры (МЭ). Решение с помощью map (C++11)

Условие задачи

Задача 5. (30 баллов)
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 Мбайт
Призеры. На соревнованиях по космическим гонкам команды космических кораблей состязаются в умении пилотировать корабли в поясе астероидов. Известно, что команд не более 100. Каждая команда имеет не более трех попыток и входные данные гарантированно корректны относительно этого ограничения. За одну попытку пилотируемый корабль за 10 минут должен обогнать как можно больше астероидов не столкнувшись с ними. Попытка считается результативной, если удалось обогнать один или более астероидов. Если корабль сталкивается с астероидом, то засчитываются все ранее пройденные астероиды, но дальнейшие попытки команда пропускает. Побеждает та команда, которая суммарно за все попытки обгонит больше всех астероидов. Напишите программу, которая помогает организаторам соревнования определить победителей. Если две команды обгоняют одинаковое число астероидов, то побеждает та, которая раньше завершила последнюю результативную попытку.
Формат входных данных
В первой строке задано суммарное количество всех попыток всех команд на соревновании. Далее в каждой строке записана информация о попытке: количество пройденных астероидов и название команды через пробел. Количество астероидов задано целым неотрицательным числом. Название команды задано строкой из цифр, прописных и строчных букв латинского алфавита без пробелов. Попытки в файле идут в порядке их завершения, т. е. чем позже завершена попытка, тем ближе она к концу файла.
Формат выходных данных
В выходной файл необходимо записать название команды победителя.

Решение

#include <fstream>
#include <string>
#include <iostream>
#include <map>
using namespace std;

int main() {
	// Карта для записи пар Ключ (имя команды) - значение (пройденные астероиды) 
	multimap<string, int> aster;
	// Рейтинговая карта. Здесь Ключ - суммарный балл, а значение - имя команды;
	// сортировка по убыванию
	multimap<int, string, greater<int>> temp;
    ifstream fin("input");
    ofstream fout("output");
	// Пропускаем первую строку 
	fin.seekg(2, ios::beg);
	// Заполняем карту:
    while (!fin.eof()) {
    	int m;
    	string s;
    	fin >> m >> s;
    	aster.emplace(s, m);
    }
    auto start = aster.cbegin();
    auto finish = aster.cend();
    while (start != finish) {
    	string s = start -> first;
    	int m = 0;
    	// Поиск производить не нужно, поскольку
    	// массив уже упорядочен по ключам
    	while (s == start -> first) {
    		m += start -> second;
    		start++;
    	}
    	// Записываем в рейтинговую карту
    	temp.emplace(m,s);
    }
    auto beg = temp.cbegin();
    int k = beg -> first;
    string s;
    // На случай, если команды будут иметь одинаковый рейтинг
    while (k == beg -> first) {
    	s = beg -> second;
    	beg++;
    }
    // Имя команды победителя отправляем в файл
    fout << s << endl;
    fin.close();
    fout.close();
    // Посмотреть что хранится в рейтинговой карте
    // можно так (из итоговой программы этот фрагмент должен быть удален)
    for (auto &r : temp) {
    	cout << r.first << " " << r.second << endl;
    }
    return 0;
}

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.


Обсуждение закрыто.