Выборы в США - 2
Вы решили задачу. Теперь можно сравнить подходы.
Сначала выбираем победителя каждого штата, затем суммируем его голоса выборщиков.
Авторский разбор для локальной версии на основе условия задачи. Это не выгрузка чужих посылок и не официальное решение исходного сайта.
Ваше принятое решение
Рекомендуемое решение: Словари голосов по штатам
Считаем бюллетени отдельно в каждом штате. При равенстве выбираем лексикографически первого кандидата; итог сортируем по убыванию голосов, затем по имени. Эти правила восстановлены по архивным тестам, поскольку краткое условие не описывает разрешение ничьих.
import sys
n = int(input())
weights = {}
for _ in range(n):
state, weight = input().split()
weights[state] = int(weight)
votes = {state: {} for state in weights}
totals = {}
for line in sys.stdin:
state, candidate = line.split()
totals.setdefault(candidate, 0)
counts = votes[state]
counts[candidate] = counts.get(candidate, 0) + 1
for state, counts in votes.items():
if counts:
winner = min(counts, key=lambda c: (-counts[c], c))
totals[winner] += weights[state]
for candidate in sorted(totals, key=lambda c: (-totals[c], c)):
print(candidate, totals[candidate])
Время: Ожидаемое O(n + v + p + k log k), n — штатов, v — бюллетеней, p — пар штат–кандидат, k — кандидатов; без учёта длины строк. Память: O(n+p+k).
Другой способ: Группировка отсортированных бюллетеней
Сортировка объединяет бюллетени по штату и кандидату. Размеры групп дают результаты штата, затем применяются те же правила ничьих и итогового порядка.
import sys
from itertools import groupby
n = int(input())
weights = {}
for _ in range(n):
state, weight = input().split()
weights[state] = int(weight)
ballots = [tuple(line.split()) for line in sys.stdin]
totals = {candidate: 0 for _, candidate in ballots}
ballots.sort()
for state, group in groupby(ballots, key=lambda r: r[0]):
counts = []
for candidate, rows in groupby(group, key=lambda r: r[1]):
counts.append((sum(1 for _ in rows), candidate))
winner = min(counts, key=lambda pair: (-pair[0], pair[1]))[1]
totals[winner] += weights[state]
for candidate in sorted(totals, key=lambda c: (-totals[c], c)):
print(candidate, totals[candidate])
Время: O(n + v log(v + 1) + k log(k + 1)), включая чтение n штатов; без учёта длины строк. Память: O(v+n+k).
На что обратить внимание
- Нельзя напрямую суммировать бюллетени по всей стране.
- Кандидаты без полученных голосов выборщиков выводятся с нулём.
- Архив содержит только два теста: правила ничьих и порядок выведены из них; поведение для штата без бюллетеней явно не задано, здесь его вес не распределяется.
Рекомендация учитывает сложность и читаемость для этой задачи. Единственного самого быстрого решения для всех размеров входа и всех компьютеров может не быть.