Задача типа #26: Обработка данных с помощью сортировки
Обработка данных с помощью сортировки
В магазине покупатель заказал очень много товаров и ему нужна помощь.
Для того чтобы унести товар нужен пакет, а в каждый отдельный пакет можно складывать только 1 товар.
Пакет можно использовать только в том случае, если вес товара не превосходит его грузоподъёмность.
Количество доступных пакетов может не совпадать с числом необходимых.
Определите какое максимальное количество товаров может унести человек, и минимальную возможную грузоподъёмность одного из пакетов, который понадобился человеку, при условии того, что количество товаров по прежнему максимально.
Входные данные:
В первой строке 2 натуральных числа: N (N≤4000) - количество товаров, которые заказал человек и M (M≤4000) - количество пакетов в доступе.
В следующих N строках находиться информация о весе товаров. А в следующих M строках - информация грузоподъёмности каждого отдельного пакета.
(Вес любого товара и грузоподъёмность любого пакета не превышают 150)
Типовой пример организации данных во входном файле:
2 3
70
140
80
90
139\
Ответом для данного примера будет - 1 80 (товар весом 140 мы унести не можем, а минимальный пакет для товара с весом 70 - 80).
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Алгоритм решения: Сортируем товары по весу (от легких к тяжелым). Сортируем пакеты по грузоподъемности (от маленьких к большим). Для каждого товара ищем самый маленький пакет, который может его унести. Использованный пакет удаляем из доступных.
Посмотреть решение задачи (код на Python) в Telegram боте по ID задачи 126015