В морском порту готовятся к перевозке грузов разной массы и формы, для этого каждый груз помещают в отдельный контейнер. Контейнеры имеют разную грузоподъемность (некоторые контейнеры могут иметь одинаковую грузоподъёмность). Из-за компьютерного сбоя из общего количества контейнеров для перевозки выделили первые попавшиеся контейнеры. Напишите программу, которая поможет посчитать максимальное количество грузов, которое можно отправить в выделенных контейнерах, и максимальную массу одного отправленного груза.
Формат входных данных:
В первой строке входного файла находится
Формат выходных данных:
Два целых неотрицательных числа: максимальное количество грузов, которое можно отправить в выделенных контейнерах и максимальную массу одного отправленного груза.
Входные данные.
В первой строке входного файла находится
Выходные данные
Два целых неотрицательных числа: максимальное число грузов и максимальную массу груза.
Типовой пример организации входных данных:
7
10 50
20 60
70 20
40 20
50 10
10 10
20 15
Для приведённого примера ответом является пара чисел: 6; 50.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Ответ:
Приведём решение на языке Python.
f = open("26_59822.txt")
s = f.readlines()
n = int(s[0])
g = []
k = []
for i in range(1,n+1):
a, b = map(int,s[i].split())
g.append(a)
k.append(b)
g.sort(reverse=True)
k.sort(reverse=True)
i = 0
j = 0
maxg = 0
while i < n:
if g[i]<=k[j]:
maxg = max(maxg, g[j])
i += 1
j += 1
else:
i += 1
print(j,maxg)
Ответ: 18456 99999.
Приведём решение Юрия Красильникова на языке Python.
gk = [list(map(int,s.split())) for s in open('26_59822.txt')][1:]
g = sorted(x[0] for x in gk) # грузы
k = sorted(x[1] for x in gk) # контейнеры
p = [] # отправленные грузы
while g and k: # пока есть грузы и контейнеры
while g and g[-1] > k[-1]: g.pop() # удаляем грузы тяжелее грузоподъемности последнего контейнера
if g: # если есть ещё груз
p.append(g.pop()) # добавляем груз в список отправленных
k.pop() # удаляем использованный контейнер
print(len(p),max(p))