День святого Валентина#10

День святого Валентина (Editorial)

Показник некрасивості — це різниця між найбільшим і найменшим діаметрами серед вибраних кульок. Отже, вигідно брати кульки, близькі за розміром.

Перше спостереження: брати більше ніж кульок ніколи не вигідно. Якщо з набору розміру викинути крайню (найбільшу або найменшу) кульку, показник некрасивості не зросте. Тому оптимально взяти рівно кульок.

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

Отже, розв'язок: відсортувати діаметри й перебрати всі вікна довжини , тобто всі від до N - K + 1, обчислюючи d_{i+K-1} - d_i. Відповідь — мінімум цих значень.

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