Что проверяет задание

Дан большой набор объектов: товары, отрезки времени, заявки, грузы. Нужно выбрать подмножество по правилу оптимальности: вместить больше, потратить меньше, обслужить раньше. Обычно это задача на сортировку и жадный выбор.

Определения

Жадный алгоритм, на каждом шаге берёт локально наилучший объект по заранее выбранному ключу и не пересматривает выбор. Он даёт глобальный оптимум только для задач, где такой ключ доказанно безопасен.

Ключ сортировки, величина, по которой упорядочивают: цена, время конца, длина, отношение цены к массе.

Вместимость, ограничение рюкзака, склада, суммы, ширины ленты. Пока объект помещается, его можно взять, иначе, пропустить.

Заявка на отрезке, объект с временем начала и конца. Две заявки совместимы, если их полуинтервалы не пересекаются.

Расписание, множество попарно совместимых заявок. Оптимум часто: наибольшее число заявок или наибольшая суммарная длина.

Последний занятый момент, для расписания это конец последней взятой заявки. Следующую можно взять, только если её начало не раньше этого момента (или строго позже, как сказано).

Группы и блоки, иногда объекты идут пакетами: скидка на каждый k-й, коробки по несколько штук. Тогда жадность работает уже по группам, а не по одиночным элементам.

Устойчивый порядок, при равном ключе сохраняется исходный порядок. Если условие при равенстве требует «меньший номер», ключ сортировки должен включать номер.

Когда какой ключ

Для наибольшего числа непересекающихся отрезков безопасный ключ, сортировка по времени окончания, затем брать каждый отрезок, который не пересекается с уже выбранным.

Для заполнения ёмкости одинаковыми «ценностями» часто сортируют по возрастанию размера и берут, пока влезает.

Для максимума стоимости при ограниченной массе жадность по стоимости или по размеру по отдельности может солгать; на экзамене обычно подбирают постановку, где ключ указан смыслом условия («самые дешёвые», «самые короткие», «кто заканчивается раньше»).

Общий алгоритм решения

1. Понять объект, ограничение и что именно оптимизируют: количество, сумму, время окончания, номер последнего взятого.
2. Выбрать ключ сортировки, который соответствует этому оптимуму.
3. Отсортировать данные. При равенстве ключа зафиксировать правило из условия.
4. Идти по списку и жадно брать объект, если он совместим с уже выбранными и с ограничением.
5. Поддержать нужные аккумуляторы: занятое место, текущий конец, счётчик, сумму.
6. Сформировать ответ из аккумуляторов. Часто просят две величины: сколько взяли и параметр последнего взятого объекта.

Программа построчно

В задании 26 файл содержит данные о большом наборе объектов: товаров, заявок, событий. Нужно смоделировать процесс из условия - чаще всего данные сначала сортируют, а потом обрабатывают по порядку, принимая на каждом шаге лучшее решение.

Разберём программу на условии:

Контейнер можно вложить в другой, если сторона внешнего больше не менее чем на 3. Блок строят от самого маленького контейнера: каждый следующий - наименьший из подходящих. Определите, сколько контейнеров в блоке, и сторону самого большого из них. В первой строке файла - количество контейнеров N, далее - N чисел.

with open("26.txt") as f:
    n = int(f.readline())
    sizes = sorted(int(f.readline()) for _ in range(n))
D = 3
chain = [sizes[0]]
for x in sizes[1:]:
    if x >= chain[-1] + D:
        chain.append(x)
print(len(chain), chain[-1])

with open("26.txt") as f: - открываем файл с данными. Подробно - в разделе «Чтение входного файла».

n = int(f.readline()) - первая строка: количество контейнеров.

sizes = sorted(int(f.readline()) for _ in range(n)) - читаем n строк, превращаем в числа и сортируем по возрастанию. Подробно - в разделе «Сортировка и ключ».

chain = [sizes[0]] - блок начинается с самого маленького контейнера.

for x in sizes[1:]: / if x >= chain[-1] + D: / chain.append(x) - идём по контейнерам от маленьких к большим и берём первый подходящий. Подробно - в разделе «Жадный выбор».

print(len(chain), chain[-1]) - количество контейнеров в блоке и последний (самый большой).

Чтение входного файла

Обычно в первой строке - параметры задачи (количество объектов, ёмкость, число ячеек), дальше - по объекту в строке.

with open("26.txt") as f:
    k, n = map(int, f.readline().split())
    requests = [tuple(map(int, f.readline().split())) for _ in range(n)]

• with open(...) as f: - файл открыт, пока выполняется вложенный блок, потом закрывается сам;
• f.readline() - следующая строка файла; .split() режет её по пробелам;
• k, n = map(int, ...) - два числа первой строки сразу в две переменные;
• [… for _ in range(n)] - прочитать ещё n строк; _ - переменная, которая не нужна (просто «n раз»);
• tuple(map(int, line.split())) - строка «120 145» превращается в пару чисел (120, 145).

Другой способ - сразу все строки списком: lines = open("26.txt").read().splitlines(). Тогда lines[0] - первая строка, lines[1:] - данные.

Сортировка и ключ

• sorted(список) - новый список по возрастанию; sorted(список, reverse=True) - по убыванию;
• список.sort() - сортирует тот же список на месте;
• key= - по чему сортировать. Для пар (начало, конец) без ключа сортировка идёт по первому числу, при равенстве - по второму.

Сортировка по нескольким столбцам:

rows.sort(key=lambda r: (r[0], -r[1]))

• lambda r: (r[0], -r[1]) - короткая функция: для строки r возвращает пару «первый столбец, минус второй»;
• сортировка сравнивает эти пары: сначала по первому столбцу по возрастанию, при равенстве - по -r[1] по возрастанию, то есть по второму столбцу по убыванию;
• после сортировки rows[k - 1] - строка с номером k (нумерация в условии с 1), rows[k - 1][1] - её второй столбец.

Жадный выбор

Жадный алгоритм на каждом шаге берёт лучший сейчас вариант и больше к выбору не возвращается. Почти всегда перед этим данные сортируют:

• «купить как можно больше изделий» - сортируем цены по возрастанию и покупаем самые дешёвые, пока хватает денег;
• «сохранить как можно больше файлов» - берём самые маленькие файлы, пока помещаются;
• «вложить как можно больше контейнеров» - идём от маленьких к большим и берём каждый подходящий.

Второй вопрос обычно уточняет выбор при равном количестве: «наибольший сохранённый файл максимально возможен». Тогда последний взятый элемент заменяют на самый большой, который ещё помещается:

limit = taken[-1] + (s - used)
best = taken[-1]
for x in files[len(taken):]:
    if x <= limit:
        best = x

s - used - оставшееся место; вместо последнего файла можно взять файл размером до taken[-1] + (s - used). Список отсортирован, поэтому последний подходящий x - самый большой.

Ячейки и время освобождения

Заявки (приход, уход) занимают ячейки. Для каждой ячейки храним, с какой минуты она свободна:

intervals.sort()
free_at = [0] * (k + 1)
served = 0
last_cell = 0
for start, end in intervals:
    for cell in range(1, k + 1):
        if free_at[cell] <= start:
            free_at[cell] = end + 1
            served += 1
            last_cell = cell
            break

• intervals.sort() - заявки по времени прихода;
• [0] * (k + 1) - список из k + 1 нулей: ячейки нумеруются с 1, нулевой элемент не используется;
• free_at[cell] <= start - ячейка уже свободна к приходу клиента; перебор с 1 даёт ячейку с наименьшим номером;
• free_at[cell] = end + 1 - ячейка освободится со следующей минуты после ухода;
• break - ячейку нашли, остальные не смотрим. Если цикл прошёл до конца без break, свободных ячеек нет - заявка отклонена (это ловят веткой else: после for).

События хронологии

Когда важно, сколько объектов «одновременно», процесс раскладывают на события: приход и уход, старт и завершение.

events = []
for s, e in processes:
    events.append((s, 1))
    events.append((e, -1))
events.sort()
cur = 0
for t, change in events:
    cur += change

• старт - событие +1, завершение - -1;
• после сортировки события идут по времени; при равном времени -1 стоит раньше +1 (кортежи сравниваются по второму элементу) - сначала завершения, потом старты;
• cur - сколько процессов выполняется в текущий момент; максимум cur - наибольшая загрузка.

Если порядок событий в одну минуту задан словами («сначала уходы, потом приходы»), его записывают в ключ сортировки: key=lambda e: (e[0], 0 if e[1] == "-" else 1).

Пары элементов

«Сколько пар, у которых сумма делится на M (i < j)»:

count = 0
for i in range(n):
    for j in range(i + 1, n):
        if (a[i] + a[j]) % m == 0:
            count += 1
print(count)

• внешний цикл выбирает первый элемент пары, внутренний - второй, правее первого: range(i + 1, n). Так каждая пара проверяется ровно один раз;
• abs(a[i] - a[j]) - модуль разности, если условие про разность.

Если нужно быстро проверять, есть ли число в наборе, набор превращают в множество: present = set(nums), тогда x in present работает мгновенно.

Подпоследовательность: динамика

«Наибольшее число контейнеров в неубывающей цепочке; брать можно только по порядку, пропуская часть». Перебрать все подпоследовательности невозможно, поэтому для каждого элемента считают ответ «цепочка, которая заканчивается этим элементом»:

dp = [1] * n
for i in range(n):
    for j in range(i):
        if a[j] <= a[i]:
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))

• dp[i] - длина лучшей цепочки, оканчивающейся элементом i; одна только i - уже цепочка длины 1;
• если элемент j левее i и a[j] <= a[i], к лучшей цепочке на j можно дописать i: длина dp[j] + 1;
• ответ - наибольшее dp[i].

Так же ищут наибольшую сумму подборки: best[i] = max(best[i], best[j] + a[i]).

Словарь рядов

Если объекты сгруппированы по рядам (места в зале, точки экрана), удобно собрать для каждого ряда свои номера:

from collections import defaultdict

rows = defaultdict(list)
for _ in range(n):
    r, s = map(int, f.readline().split())
    rows[r].append(s)

• defaultdict(list) - словарь, в котором для нового ключа сам создаётся пустой список; не нужно проверять if r in rows;
• defaultdict(set) - то же с множествами: повторы отбрасываются автоматически;
• дальше каждый ряд обрабатывают отдельно: for r in sorted(rows):, номера ряда сортируют и проверяют соседей через zip(taken, taken[1:]) - пары (текущий, следующий).