Language issues#209

Language issues (Editorial)

Спочатку розберемося з перевіркою для фіксованого : чи можна скласти пар, маючи перших волонтерів?

Тут працює жадібність. Відсортуємо учнів за зростанням рівня, а доступних волонтерів — за спаданням. Тепер зіставимо найслабшого учня з найсильнішим волонтером, другого за слабкістю — з другим за силою і так далі. Якщо хоч одна з цих пар не дотягує до , то розбиття не існує взагалі.

Чому це коректно? Найслабший учень потребує найсильнішого партнера; віддавши найсильнішого волонтера комусь іншому, ми лише ускладнимо задачу. Стандартний обмінний аргумент показує, що таке зіставлення не гірше за будь-яке інше.

Тепер друге спостереження: перевірка монотонна. Якщо з першими волонтерами пари скласти вдалося, то з j+1 поготів — зайвий волонтер нікому не заважає. Тому мінімальне шукається двійковим пошуком у діапазоні від до .

Якщо n > m або навіть при j = m пари не складаються, виводимо .

Складність — \mathcal{O}\bigl((n + m)\log^2\bigr) у прямій реалізації або \mathcal{O}(m \log m + n \log m), якщо заздалегідь відсортувати волонтерів за рівнем разом з їхніми початковими номерами й на кожній перевірці брати лише тих, чий номер менший за .