Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

26. Прикладная задача: В один контейнер может быть упакован только один груз

Задание #298073
Решено верно
Решено неверно
Сообщить о проблеме

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

Входные данные

В первой строке входного файла находятся два натуральных числа $N$ ($N \le 1000$) и $M$ ($M \le 1000$) – количество грузов и количество контейнеров соответственно. Следующие $N$ строк содержат числа, обозначающие массы грузов, затем идут $M$ строк, где указана максимально допустимая масса груза для размещения в конкретном контейнере. Числа $M$ и $N$ могут быть не равны.

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

Типовой пример организации данных во входном файле:

5 6
160
130
120
150
100
150
50
155
99
100
170

При таких исходных данных максимальное количество грузов, которые могут быть упакованы в контейнеры, равно $4$. При этом масса самого тяжёлого груза составит $160$, а упакованными окажутся грузы массой, например, $160$, $130$, $120$ и $100$ – в контейнеры, выдерживающие массу $170$, $150$, $155$ и $100$.

Первая часть — жадность. Отсортируем и грузы, и контейнеры по возрастанию, затем пройдём по контейнерам от меньшего к большему, каждый раз пытаясь положить в него самый лёгкий ещё не упакованный груз. Если он влезает, груз упакован, переходим к следующему. Это даёт максимальное количество, обозначим его $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$.

Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение