Разбор задания 26 демонстрационного варианта 2022 года
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя. По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные
В первой строке входного файла 26.txt находятся два числа: S – размер свободного места на диске (натуральное число, не превышающее 100 000) и N – количество пользователей (натуральное число, не превышающее 10000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке. Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример входного файла:
100 4
80
30
50
40
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар – 50, поэтому ответ для приведённого примера:
2 50
Идея решения
1) Так как необходимо сохранить файлы максимального числа пользователей, следовательно, будем брать файлы тех пользователей, чьи объемы как можно меньше. Тогда суммарно мы наберем требуемый объем, используя как можно больше файлов.
2) Набирать файлы будем до тех пор, пока сумма их объемов будет меньше свободного места на архивном диске.
3) После набора нужного объема, скорее всего у нас останется некоторая разница (
\(\triangle\)). Благодаря этой разнице мы можем заменить один файл другим, с бОльшим объемом.
4) Заменять нужно файл с самым большим объемом. Почему? Необходимо заменить таким образом, чтобы разница между файлами была не больше, чем
\(\triangle\). То есть должно выполняться условие
\(X - x <= \triangle\), где
X - значение, которым заменяем,
х - значение, которое будем заменять. Анализируя данное выражение, можно легко понять, что при бОльшем
X мы заменим бОльшее
x.
Словесный алгоритм
1) Считываем данные из первой строки в переменные S и N.
2) Считываем данные в массив.
3) Отсортируем исходный массив по возрастанию.
4) Проходим по массиву и одновременно подсчитываем сумму элементов, пока она меньше либо равна S.
5) Останавливаем перебор по массиву в тот момент, когда очередное значение при добавлении к сумме, даст превышение значения S.
5) Вычисляем разницу (
\(\triangle\)) между подсчитанной суммой и S.
6) Идем дальше по массиву и ищем
максимальное значение, у которого выполняется условие
\(X - x <= \triangle\).
Реализуйте данный словесный алгоритм самостоятельно.