Для перевозки партии грузов различной массы выкупают место у компании, которая организует перевозку на грузовых судах. Судно не может принять на борт больше S тонн груза. Известно, что отдельный груз нельзя разделить для перевозки, то есть один груз должен доставляться одним рейсом на одном грузовом судне. В первую очередь перевозятся грузы как можно большей массы.
За какое минимальное количество рейсов можно перевезти все грузы?
Входные данные представлены в файле следующим образом. В первой строке входного файла записаны два целых числа: N — общее количество грузов и S — грузоподъёмность судна в тоннах. Каждая из следующих N строк содержит одно целое число < S — массу груза в тоннах. В ответе запишите два числа — минимальное количество рейсов и суммарную массу грузов, которые будут перевезены последним рейсом.
Пример входного файла:
6 500
140
150
160
200
220
240
Первым рейсом будет отправлено 2 груза — 240 и 220, вторым — 200, 160 и 140, третьим — 150. При таких входных данных ответ будет 3 и 150.
with open(’26.txt’, ’r’) as f:
number, load = map(int, f.readline().split()) # Читаем количество грузов и грузоподъемность
# Читаем грузы
all_cargo = []
for _ in range(number):
all_cargo.append(int(f.readline()))
all_cargo.sort(reverse=True)
count = 0
while len(all_cargo):
cargo = all_cargo[0]
del(all_cargo[0])
# Забираем самый тяжелый груз
count += 1
# Если есть грузы, которые поместятся еще на этот рейс, забираем и их
vz = []
for i in range(len(all_cargo)):
if all_cargo[i] + cargo <= load:
cargo = cargo + all_cargo[i]
vz.append(i)
# удаляем те грузы, которые только что забрали
for i in range(len(vz)):
x = vz[i] - i # вычитаем i так как после удаления очередного элемента индексация смещается
print(x, len(all_cargo))
del(all_cargo[x])
print(count, cargo)