Расстановка экспонатов

Автор задачи и разработчик: Даниил Орешников

Упорядочим все экспонаты по высоте, теперь $$$h_1 \leqslant h_2 \leqslant \ldots \leqslant h_n$$$. Заметим, что достаточно рассмотреть только $$$H = h_i$$$ для некоторого $$$i$$$, так как любое другое значение $$$H$$$ можно опустить вниз до ближайшего $$$h_i$$$, не изменив множество, которое им ограничено.

Будем перебирать все возможные значения $$$H$$$ по возрастанию от $$$h_{\frac{n}{2}}$$$ до $$$h_n$$$. Перебирать меньшие $$$h_i$$$ тоже не имеет смысла, потому что тогда вне зависимости от $$$W$$$ под критерий будет попадать строго меньше половины экспонатов.

Для очередного $$$H = h_i$$$, проверим, можно ли выбрать такое $$$W$$$, чтобы под описанный в условии критерий подходила ровно половина экспонатов. Для этого рассмотрим множество всех экспонатов с высотой $$$\leqslant H$$$, упорядочим их по высоте, и проверим, что ширина экспоната на позиции $$$\frac{n}{2}$$$ отличается от ширины экспоната на позиции $$$\frac{n}{2} + 1$$$.

Если они не отличаются, то не существует подходящего $$$W$$$. Действительно, мы не можем выбрать значение меньше ширины $$$\frac{n}{2}$$$-го экспоната, и не можем выбрать большее либо равное, потому что под такой критерий подходит уже хотя бы $$$\frac{n}{2} + 1$$$ экспонат. Если же эти две ширины оказались различными, то мы нашли еще один способ разбить экспонаты на два множества.

Однако, есть еще одна деталь, которую стоит учесть — не факт, что мы нашли действительно новый способ разбиения. Если при полученном $$$W$$$, равном $$$\frac{n}{2}$$$-й по величине ширине экспоната, ни один экспонат с высотой, равной $$$H$$$, не вошел в первую группу, то такой способ уже был посчитан ранее. Таким образом, необходимо так же проверить, что выбранный $$$W \geqslant \min\limits_{j:\, h_j = H}(w_j)$$$.

Осталось реализовать эту проверку за короткое время. Как и уже было сказано, будем рассматривать экспонаты по увеличению $$$h_i$$$. И будем поддерживать дерево поиска (например, декартово) по ширине на всех уже рассмотренных экспонатах. Когда встречаем следующее по величине значение $$$h_i$$$, добавляем в декартово дерево ширину каждого экспоната с такой высотой, после чего проверяем, что выполняется описанное выше свойство.

Время работы решения — $$$\mathcal{O}(n \log n)$$$.