Задание 26. Информатика. 2022-8
Илье необходимо перенести файлы с одного компьютера на другой при помощи внешнего жёсткого диска.
Объём диска может быть меньше, чем требуется для переноса файлов за один раз. Свободный объём на диске и размеры файлов известны.
По заданной информации об объёме файлов на компьютере и свободном объёме на диске определите максимальное число файлов, которые могут быть перенесены за один раз на внешний жесткий диск, а также максимальный размер файла, записанного на этот диск, при условии, что перенесено наибольшее возможное число файлов.
Входные данные
В первой строке входного файла находятся два числа: \(S\) — размер свободного места на диске (натуральное число, не превосходящее \(100~000\)) и \(N\) — количество файлов, которые надо перенести (натуральное число, не превышающее \(10~000\)). В следующих \(N\) строках находятся значения объёмов указанных файлов (все числа натуральные, не превышающие \(100\)), каждое в отдельной строке.
Выходные данные
Запишите в ответе два числа: сначала наибольшее число файлов, которые могут быть перенесены на внешний жёсткий диск за один раз, затем максимальный размер перенесённого файла, при условии, что перенесено наибольшее возможное число файлов. Если вариантов переноса несколько, выберите тот, при котором будет перенесён наибольший файл.
Пример входного файла:
\(100\) \(4\)
\(80\)
\(30\)
\(50\)
\(40\)
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов: \(30\) и \(40\), \(30\) и \(50\) или \(40\) и \(50\). Наибольший объём файла из перечисленных пар — \(50\), поэтому ответ для приведённого примера:
\(2\) \(50\)
Решение:
Python
f = open('input26_08.txt')
S, N = tuple(map(int, f.readline().split()))
file_size = list(map(int, f.readlines()))
file_size.sort()
num_files = 0 # число файлов, которое можно записать на диск
max_size = 0 # максимальный размер файла
used_cap = 0 # использованное место на диске
curr_file = 0 # текущий номер файла
for i in range(N):
if used_cap + file_size[i] <= S: # пока есть место на диске
used_cap += file_size[i] # записываем файл, учитываем это в использованном объеме
max_size = file_size[i] # максимальный размер файла - размер последнего записанного
else: # место на диске закончилось
num_files = i # количество записанных файлов (i=0,1,2,... а кол-во записанных файлов 1,2,3,...)
curr_file = i - 1 # номер элемента массива для последнего записанного файла
break
if used_cap < S: # если на диске осталось свободное место
used_cap -= file_size[curr_file] # удаляем последний записанный файл
for i in range(N-1, curr_file-1, -1): # и пытаемся записать на его место файл большего размера
if used_cap + file_size[i] <= S: # если это удается, обновляем размер использованного объема
used_cap += file_size[i]
max_size = file_size[i] # максимальный размер файла - это размер последнего записанного файла
break
print(num_files, max_size)
Ответ: \(3105\) \(75\)