Как решать №26 из ЕГЭ по информатике?

1. Введение

Разберём на примере демо2021

Текст задачи:
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя. По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные. В первой строке входного файла 26.txt находятся два числа: S – размер свободного места на диске (натуральное число, не превышающее 100 000) и N – количество пользователей (натуральное число, не превышающее 10 000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример входного файла:
100 4 80 30 50 40
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар – 50, поэтому ответ для приведённого примера: 2 50

2. Основы работы с файлами и извлечение данных

Для начала научимся считывать файлы.
В Python, чтобы считать файл, нужно открыть этот файл. Логично?)
Пример открытия файла:

f = open("path_to_the_file")

f - файловая переменная, "path_to_the_file" - путь к файлу.
P.S: Если текстовый файл лежит в одной директории с py-файлом, то достаточно указать только его имя.

В нашем случае это будет выглядеть так:

f = open("26.txt")

Теперь перейдём к считыванию файла построчно!

Пример:

f = open("26.txt")
print(f.readline())

Output:

8200 970

Давайте заведём переменные S(сумма) и N(кол-во чисел)

S, N = map(int, f.readline().split())

Подробнее о map можно посмотреть тут

Теперь давайте сделаем список размера N и заполним его содержимым из 26.txt, используя генератор списка:

files = [int(f.readline()) for _ in range(N)]

f.close()

3. Основной алгоритм

Разберём пример из задачи:

100 4 80 30 50 40

Для начала возьмём файл размером 80, чтобы заполнить архив ему нужен в пару файл, у которого размер не более 100-80=20. Такого файла нет! Значит, мы учитываем 80 в ответ!

Теперь аналогичные операции проводим с числом 30. Ему в пару нужен файл с размером не более 100-30=70. Этому условию удовлетворяют 40 и 50. Однако максимальное заполнение архива будет при упаковки файлов 30 и 50. Максимальный из них 50.

Всё то же самое с 40, ему не хватает файла не более 60. Этому условию удовлетворяют 30 и 50. Однако максимальное заполнение архива будет при упаковки файлов 40 и 50. Максимальный из них 50.

Итого: наибольшее число пользователей, чьи файлы могут быть помещены в архив, равно 2, а максимальный размер имеющегося файла, который может быть сохранён в архиве, равен 50.

4. Реализация

Для начала отсортируем список files методом sort:

files.sort()

Заведём переменные scur, отвечающую за текущую сумму, и i, которая будет одновременно хранить и кол-во пользователей, чьи файлы могут быть помещены в архив. ОБНУЛИМ ИХ!

scur, i = 0, 0

Теперь создадим список cand, где будут храниться файлы, которые можно поместить в архив.

cand = []

Просуммируем первые числа пока их сумма меньше общей суммы S и добавляем данные числа в cand. Если сумма превысит S, выходим из цикла.

while scur<s:
    if scur+files[i]<=s:
        scur+=files[i]
        i+=1
        cand.append(files[i])
    else:
        break

Вычислим оставшися объём архива без последнего файла.

file = s - (scur-files[i])

Попробуем "добить" архив по полной)

for j in range(i+1, N):
    if file>=files[j]:
        cand.append(files[j])

Последний рывок! Печатаем ответ

print(i, max(cand))

Вот весь код программы

f = open("26.txt")
S, N = map(int, f.readline().split())
files = [int(f.readline()) for _ in range(N)]
f.close()

scur, i = 0, 0
cand = []

while scur<s:
    if scur+files[i]<=s:
        scur+=files[i]
        i+=1
        cand.append(files[i])
    else:
        break

file = s - (scur-files[i])

for j in range(i+1, N):
    if file>=files[j]:
        cand.append(files[j])

print(i, max(cand))

Output:

568 50

Редактор: @IZPROGRAMMER