Заправки по пути
Грузовик едет по прямой трассе от отметки 0 до отметки T километров. В баке F литров, литра хватает на километр, бак бездонный. По дороге есть заправки: на отметке p можно залить ровно g литров — сколько осталось в цистерне станции. Какое наименьшее число остановок нужно, чтобы доехать? Если доехать нельзя, выведите −1.
В первом примере выгодно остановиться на первой станции и залить 50 литров. Тот, кто едет до самой дальней достижимой станции, заедет на отметку 50, получит там 10 литров и застрянет: щедрая станция осталась позади.
Вход
В первой строке T, F и число станций n (1 ≤ T, F ≤ 10⁹, 0 ≤ n ≤ 2·10⁵). Дальше n строк с p и g (0 < p < T, 1 ≤ g ≤ 10⁹), станции по возрастанию p.
Выход
Наименьшее число остановок или −1.
Примеры
Пример 1
100 50 2 10 50 50 10
1
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Не обязательно решать, где остановиться, в тот момент, когда проезжаешь станцию. Можно решить потом — когда топливо кончится.
2Идея
Едем, пока хватает топлива, и запоминаем все станции, которые проехали. Когда до следующей точки не дотянуть, делаем вид, что заправились на самой щедрой из проеханных станций, — и берём её топливо. Проеханные станции держим в куче по объёму: самая щедрая наверху.
3Разбор
Почему это оптимально? Пусть мы сделали k остановок и доехали до отметки x. Жадность гарантирует: среди всех способов выбрать k станций из тех, что левее x, наш набор даёт больше всего топлива — мы каждый раз брали самое большое из доступного. Значит, и дальше всех на k остановках не уедет никто. Это аргумент «жадность не отстаёт»: на каждом шаге жадный ответ хотя бы не хуже любого другого, и так до финиша.
Правило «заправляться на самой дальней доступной станции» выглядит разумно, но оно забывает станции позади. Первый пример показывает, что оно может застрять там, где проехать можно.
Цель удобно добавить как последнюю станцию с нулём литров: тогда проверка «доедем ли до конца» — та же, что и для любой станции. Сумма топлива доходит до 2·10¹⁴ — в Go нужен int64.
3+Решение
4Сложность
Каждая станция один раз попадает в кучу и не больше одного раза из неё выходит: O(n log n).
5Типичные ошибки
- Самая дальняя станция. Проезжает мимо щедрых станций и застревает там, где доехать можно: первый пример, шестой тест.
- Заправляться везде, где можно. Доедет, если вообще можно доехать, но остановок будет намного больше.
- Финиш между станциями. Проверка «хватит ли до цели» нужна так же, как и проверка до станции: иначе можно выдать ответ, не доехав.
Алгоритмы задачи
обычно O(n log n): сортировка или куча
2 задачи
DS
Структура данных
Двоичная куча
Минимум под рукой, добавление и извлечение за O(log n): дерево в массиве, на котором живут календари событий.
O(log n)
2 задачи