Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов.…
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя. По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей. Входные данные. Задание 26 В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 10 000) и N — количество пользователей (натуральное число, не превышающее 2000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке. Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей. Пример входного файла: 100 4 80 30 50 40 При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов — 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар — 50, поэтому ответ для приведённого примера: 2 50
Давайте подробно разберём задачу и пошагово решим её.
Задача:
Нам даны объёмы файлов пользователей и общий объём свободного места на диске. Требуется определить:
- Максимальное число пользователей, чьи файлы можно сохранить в архиве, не превышая свободное место.
- При этом, из файлов выбранных пользователей, среди которых достигнуто максимум возможного количества, определить максимальный размер файла.
Пояснение и стратегиия
Чтобы решить задачу, можно воспользоваться следующим подходом:
Отсортировать списки файлов по возрастанию. Это позволит сначала выбирать самые маленькие файлы, чтобы максимально увеличить количество файлов, которые мы можем поместить, а затем искать максимальный размер файла среди выбранных.
Накопительно брать файлы, начиная с самых маленьких, и считать их сумму. Когда сумма станет больше свободного места, значит, мы не можем добавить следующий файл.
После того как мы нашли максимум файлов, которые можно поместить, среди них определить максимальный размер файла — это последний добавленный файл (если мы выбираем в порядке возрастания).
Алгоритм пошагово
Считать входные данные: свободное место
S, число пользователейNи список объёмов файлов.Отсортировать список объёмов по возрастанию.
Проходить по отсортированному списку, суммируя файлы, пока сумма не превысит
S. Запомнить индекс последнего включённого файла.Количество файлов — это количество файлов, выбранных до достижения суммы, превышающей
S.Максимальный размер файла — это последний файл, включённый в выбранное множество.
Пример
Входные данные:
100 4
80
30
50
40
Обработка:
- Отсортируем: 30, 40, 50, 80
- Сумма поэлементно:
- 30 → сумма = 30
- 40 → сумма = 70
- 50 → сумма = 120 (превысила 100, значит, мы не можем взять 50)
Изначально мы можем взять только первые два файла (30 и 40), сумма которых равна 70, что не превышает 100.
- Максимальное число файлов: 2
- Максимальный размер файла среди выбранных (30 и 40): 40
Ответ: 2 40
Реализация на Python
def max_files_and_max_size(S, N, file_sizes):
# Сортируем размеры файлов
sorted_files = sorted(file_sizes)
total = 0
count = 0
# Перебираем файлы, пока сумма не превысит S
for size in sorted_files:
if total + size <= S:
total += size
count += 1
else:
break
# Максимальный размер файла среди выбранных
max_size = sorted_files[count - 1] if count > 0 else 0
return count, max_size
# Ввод данных
S, N = map(int, input().split())
file_sizes = [int(input()) for _ in range(N)]
# Вызов функции и вывод результата
result = max_files_and_max_size(S, N, file_sizes)
print(result[0], result[1])
Если есть вопросы или нужно решение для другого примера, могу помочь!
