Алгоритм решения задания 14. Часть 1
Учимся решать 15 задания первого типа
Читать
Организаторам спортивных соревнований необходимо доставить как можно большее число команд в некоторый город. Для доставки используются самолёты определённой пассажировместимости. Входной файл содержит сведения о количестве человек в команде и о пассажировместимости самолётов, которые имеются в наличии. Из соображений безопасности в одном самолёте может лететь только одна команда. Найдите способ доставить на соревнования максимально возможное число команд. Если способов несколько, то нужно выбрать такой, чтобы можно было доставить команды с максимальным числом участников.
Входные данные.
В первой строке входного файла находятся два натуральных числа N (N ≤ 1000) и M (M ≤ 1000) – количество команд и количество самолётов соответственно. Следующие N строк содержат числа, обозначающие количество человек в команде, затем M строк, где указана пассажировместимость самолётов. Числа M и N могут быть не равны.
Запишите в ответе два натуральных числа: сначала максимальное количество команд, которые могут прибыть на соревнования, затем максимальную численность команды в этом случае.
Правильный ответ:
679 194496
with open('2623.txt') as file:
N, M = map(int, file.readline().split())
teams = [int(file.readline().strip()) for _ in range(N)]
planes = [int(file.readline().strip()) for _ in range(M)]
# Сортируем команды по убыванию (чтобы при равном количестве брать самые большие)
teams.sort(reverse=True)
# Сортируем самолёты по убыванию (берём самые большие подходящие)
planes.sort(reverse=True)
taken_teams = [] # размеры взятых команд
team_idx = 0 # указатель по отсортированным командам
for plane in planes:
# Ищем первую (самую большую) команду, которая влезает
while team_idx < len(teams) and teams[team_idx] > plane:
team_idx += 1
if team_idx < len(teams):
# Берём эту команду
taken_teams.append(teams[team_idx])
team_idx += 1 # переходим к следующей (меньшей) команде
count = len(taken_teams) # сколько команд
max_team_size = max(taken_teams) # размер самой большой команды
print(count, max_team_size)
