Выбор ответа Senior Жадные обновлено
Заправки по кругу
Вопрос
Задача о заправках на кольце: gas[i] и cost[i]. Если суммарно бензина меньше расхода, ответа нет. Иначе как найти старт за O(n)?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Идём с балансом; ушёл в минус на i, старт переносим на i + 1. Если из старта s мы не доехали до i, то и из любой станции между s и i не доедем: к ним мы приезжали с неотрицательным запасом.
Варианты ответа
- Идём с балансом; ушёл в минус на i, старт переносим на i + 1правильный ответ
- Пробовать старт с каждой станции, O(n²), быстрее нельзя
- Стартовать со станции с максимальным
gas[i], там больше всего топлива - Стартовать со станции с минимальным
cost[i], там дешевле всего ехать
Разбор
Если из старта s мы не доехали до i, то и из любой станции между s и i не доедем: к ним мы приезжали с неотрицательным запасом. Поэтому все они отбрасываются разом. При суммарном балансе не меньше нуля последний кандидат и есть ответ.
- O(n²) можно улучшить, как показано.
- Максимальный
gasне учитывает расходы на следующих участках. - Минимальный
costтоже локальный признак без гарантии.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.