26. Прикладная задача: В один контейнер может быть упакован только один груз
Входной файл содержит сведения о массе грузов, поступивших в транспортную компанию, и о параметрах контейнеров, которые у неё имеются. В один контейнер может быть упакован только один груз. Найдите способ для распределения максимального количества грузов по контейнерам. Если способов несколько, то нужно выбрать такой, чтобы можно было упаковать наиболее тяжёлый груз.
Первая часть — жадность. Отсортируем и грузы, и контейнеры по возрастанию, затем пройдём по контейнерам от меньшего к большему, каждый раз пытаясь положить в него самый лёгкий ещё не упакованный груз. Если он влезает, груз упакован, переходим к следующему. Это даёт максимальное количество, обозначим его $K$.
Вторая часть требует отдельной проверки. Спрашивается не про самый тяжёлый груз какого-то одного оптимального распределения, а про максимально возможный среди всех распределений размера $K$. Идём по грузам от самого тяжёлого к более лёгким и для каждого проверяем: можно ли включить его в распределение, не потеряв в количестве.
Тут важна деталь — какой контейнер отдать кандидату. Отдавать надо наименьший из подходящих, то есть первый контейнер с грузоподъёмностью не меньше массы кандидата. Большие контейнеры полезнее для остальных грузов, поэтому забирать их из общего пула невыгодно. После этого пересчитываем жадность на оставшихся грузах и контейнерах: если получилось ровно $K-1$, кандидат подходит, и это ответ.
from bisect import bisect_left
def match(goods, cans): # макс. число упакованных грузов
i, cnt = 0, 0
for c in cans: # контейнеры по возрастанию
if i < len(goods) and goods[i] <= c:
cnt += 1
i += 1
return cnt
f = open('26-19.txt')
n, m = map(int, f.readline().split())
goods = sorted(int(f.readline()) for _ in range(n))
cans = sorted(int(f.readline()) for _ in range(m))
K = match(goods, cans)
best = None
for idx in range(len(goods)-1, -1, -1): # кандидат на самый тяжёлый груз
w = goods[idx]
j = bisect_left(cans, w) # наименьший подходящий контейнер
if j == len(cans):
continue
if match(goods[:idx] + goods[idx+1:], cans[:j] + cans[j+1:]) == K - 1:
best = w
break
print(K, best) # 791 197491
Проверка. Грузов $853$ массой от $91534$ до $199595$, контейнеров $796$ грузоподъёмностью от $90045$ до $197604$. Упаковать удаётся $791$ груз. Девять самых тяжёлых грузов, начиная с $198262$, не помещаются ни в один контейнер вообще, поэтому кандидатом становится следующий по массе — $197491$, и для него подходящий контейнер находится. На типовом примере из условия программа выдаёт $4$ и $160$.