Нове захоплення Степана#161

Нове захоплення Степана (Editorial)

Усередині набору важливі лише дві величини: найкоротший і найдовший олівець. Тому замінимо кожен набір на відрізок [l_i, r_i], де l_i = \min, а r_i = \max довжин у ньому.

Якщо вибрано наборів, то найкоротший олівець у коробці дорівнює \min l_i, а найдовший — \max r_i по вибраних. Отже, треба вибрати рівно відрізків, мінімізуючи

\max_{i \in S} r_i - \min_{i \in S} l_i.

Зафіксуємо нижню межу: нехай — значення \min l_i серед вибраних. Тоді брати можна лише набори з l_i \ge L, і серед них вигідно взяти ті , у яких найменші r_i; відповідь для цього дорівнює (-те за величиною найменше ) .

Це підказує замітання справа наліво. Відсортуємо набори за і переберемо у порядку спадання, щоразу додаючи набори з поточним . Підтримуватимемо купу (max-heap) розміру , у якій лежать найменших значень серед уже доданих: додаючи новий , кладемо його в купу, а якщо розмір перевищив — виштовхуємо найбільший елемент.

Щойно в купі рівно елементів, її вершина — це потрібний максимум , і ми оновлюємо відповідь значенням «вершина ».

Складність — \mathcal{O}(N \log N): сортування плюс операції з купою. Сумарна кількість олівців обмежена умовою, тому зчитування наборів теж укладається в ліміт — головне не зберігати всі олівці, а одразу згортати кожен набір у пару .