Жадность № 2

Теперь перейдём к возможным решениям исходной задачи. Несколько полезных фактов:

Решение за \(O(N^2\log N)\), пока без доказательства: всех обычных людей будем по очереди пытаться добавить в \(P\). За \(O(N\log N)\) той же жадностью, что и раньше, будем проверять, можно ли распределить по самолётам всех уже распределенных и ещё одного нового. Полученный ответ оптимален. Но пока не понятно, почему.

Чтобы развивать мысль дальше, заметим, что задачу можно читать как «Дан двудольный граф, найдите максимальное паросочетание, содержащее такие-то вершины». Двудольный граф — это отрезки и места в самолетах. Каждому отрезку \([a_i,b_i]\) соответствует \(k\cdot(b_i-a_i+1)\) свободных мест. В этом графе \(O(nm)\) ребер, а максимальное паросочетание имеет размер не более \(n\).

Паросочетание можно искать алгоритмом Куна (работает за \(O(VE)\)), о нём можно прочесть по ссылке: http://e-maxx.ru/algo/kuhn_matching). Коротко алгоритм можно описать так: по очереди перебираем вершины первой доли, не входящие в паросочетание. Если вершину можно добавить, добавляем (автоматически добавится и ещё одна из второй доли, а паросочетание как-то перестроится). Для нас самое важное, что множество вершин в паросочетании только расширяется. Значит, если участников РОИ распределить по свободным местам жадно, а потом увеличить паросочетание алгоритмом Куна до максимального, мы получим верный ответ. В частности мы получили решение вида «применить в лоб общий вариант алгоритма Куна», работающее за \(O(VE)=O(n^2m)\), и доказали корректность алгоритма за \(O(n^2\log n)\) — это просто одна из возможных реализаций алгоритма Куна на нашем графе. Ещё важно увидеть, что любое распределение (например, \(P\) и \(M\)) — это паросочетание, а любое паросочетание — это возможное распределение людей по свободным местам.

Решение за \(O(n\log n)\) (для понимания необходимо понимать алгоритм Куна!)

Другое решение за \(O(n\log n)\)