Теория:
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов.
Известно, какой объём занимает файл каждого пользователя. По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определи максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные
В первой строке входного файла находятся два числа: \(S\) — размер свободного места на диске (натуральное число, не превышающее \(10~000\)) — и \(N\) — количество пользователей (натуральное число, не превышающее \(1000\)). В следующих \(N\) строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие \(100\)), каждое — в отдельной строке.
Запиши в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем — максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Данные для решения: demo_22.txt.
План решения
1. Из приложенного файла считаем объём диска \(S\) и количество пользователей \(N\).
2. В список \(A\) сохраним объёмы файлов пользователей и список отсортируем по возрастанию.
3. Так как нам нужно максимальное количество файлов пользователей сохранить на диске, последовательно из общего объёма диска будем отнимать объёмы файлов, начиная с наименьших.
4. Одновременно в цикле п. \(3\) будем определять количество пользователей, чьи файлы сохранены (с), и максимальный сохранённый элемент (aMax).
5. Удалив из полученной суммы максимальный элемент, в оставшемся отсортированном списке ищем максимальный элемент \(A[j]\), который вместе с накопленной суммой не выйдет из объёма диска \(S\).
Рис. \(1\). Программа
Рис. 1. Программа. © ЯКласс.