Апельсини#508

Апельсини (Розбір)

Автор, розробник, автор розбору: Андрій Столітній

Розглянемо випадок, коли ми маємо зібрати всі апельсини в координаті .

Для кожного апельсину ми маємо прийти до нього і прийти назад. Йти не в напрямку з апельсином не є оптимальним. Тоді ми маємо для кожного апельсину повторити маршрут k \rightarrow x_i \rightarrow k.

Відповідь виглядає як 2 \sum_{i=1}^{n} |x_i - k|, що можна розбити на

2 \left( \sum_{x_i \le k} (k - x_i) + \sum_{x_i > k} (x_i - k) \right)
2 \left( \sum_{x_i \le k} k - \sum_{x_i \le k} x_i + \sum_{x_i > k} x_i - \sum_{x_i > k} k \right).

Тоді нам треба підтримувати такі прості суми. Можемо йти від найменшого до найбільшого, тоді підтримка таких сум буде очевидно.

Загальна складність: .