Задание EGEINFD8A5BB: Сортировка, отбор и моделирование

Решение.

Сохраним приложенный текстовый файл под именем data.txt. Первая строка задаёт параметры задачи; её нельзя считать обычной записью данных. В программе нумерация элементов списка начинается с нуля, а номера из условия сохраняются без сдвига.

Заголовок задаёт N = 853 грузов и M = 796 контейнеров. Сначала читаем N масс, затем M грузоподъёмностей. Эти количества различны, и один контейнер вмещает только один груз.

Сортируем грузы и контейнеры по убыванию. Если самый тяжёлый оставшийся груз превышает наибольшую оставшуюся грузоподъёмность, он не поместится никуда: пропускаем груз. Иначе помещаем его в самый вместительный контейнер и переходим к следующему контейнеру.

Такой шаг сохраняет максимально возможное количество пар. Если в оптимальном распределении тяжёлый груз и самый вместительный контейнер заняты другими партнёрами, их можно переставить: более лёгкий груз поместится в контейнер, выдерживавший тяжёлый. Если один из них не использован, достаточно одной замены. Если оба свободны, добавление пары улучшило бы якобы оптимальное распределение.

Следовательно, жадное распределение максимально по количеству. Оно включает самый тяжёлый груз, который вообще помещается в наибольший контейнер, и тем самым оптимизирует второй критерий. Время O(N log N + M log M), память O(N + M).

Полная программа на Python:

with open("data.txt", encoding="utf-8-sig") as f:
    n, m = map(int, f.readline().split())
    weights = sorted((int(f.readline()) for _ in range(n)), reverse=True)
    capacities = sorted((int(f.readline()) for _ in range(m)), reverse=True)
count = 0
heaviest = 0
for weight in weights:
    if count < m and weight <= capacities[count]:
        heaviest = max(heaviest, weight)
        count += 1
print(count, heaviest)

Проверка результата.

Упаковано 791 грузов. Первые три назначения (номера грузов и контейнеров считаются отдельно с единицы):

В каждой из 791 пар масса не превышает грузоподъёмности, каждый номер используется один раз. Максимальная масса выбранного груза 197491.

Ответ: 791 197491.