Road to a new life.#7

Road to a new life. (Editorial)

Головна умова, яку легко проґавити: різні види бензину не можна змішувати. Отже, приїхавши на заправку, Петрик мусить мати порожній бак, а весь куплений там бензин має бути витрачений до наступної заправки, де він заправляється.

Тому маршрут розбивається на послідовні відрізки: кожен відрізок починається на якійсь заправці й повністю проїжджається на її пальному. Вартість відрізка від заправки до наступної точки заправки дорівнює

(x_B - x_A) \cdot w \cdot c_A.

Мінімізація вартості. Стоячи на заправці з ціною , немає сенсу переїжджати на дорожчу заправку — це лише збільшить ціну кожного кілометра. Натомість, щойно попереду з'явиться заправка з ціною строго меншою, вигідно доїхати саме до неї й далі їхати дешевшим пальним. Отже, оптимальний план — рухатися від поточної заправки до першої заправки з не більшою ціною, і так до кінця.

Мінімізація бака. Розмір бака має вміщувати найдовший відрізок: для відрізка довжини потрібно L \cdot w літрів. Тому відповідь — максимум L \cdot w по всіх відрізках плану.

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

Реалізація: відсортувати заправки за координатою, пройтися зліва направо, тримаючи поточну заправку; щойно трапилась заправка з ціною поточної, зафіксувати довжину відрізка й перейти на неї. Наприкінці не забути останній відрізок — до самого пункту призначення .

Складність — \mathcal{O}(n \log n) через сортування. Добуток d \cdot w сягає 10^{12}, тому обов'язково 64-бітний тип.