Что спрашивают
Робот едет вперёд из 0 в R. Заряда хватает на V, в начале батарея полная, на каждой станции её можно полностью зарядить. Расстояние ровно V допустимо.
Найдите минимум зарядок, затем минимальную координату последней станции. N ≤ 100 000, R ≤ 10^9, V < R, координаты различны и меньше R. Доехать гарантированно можно.
Приём решения
Для минимального числа остановок обычный жадный шаг — ехать к самой дальней достижимой станции. После одинакового количества зарядок такая позиция не меньше позиции любого другого маршрута, значит возможностей впереди не меньше.
Отсортируем станции и указателем просмотрим все координаты не дальше position + V. Если с самой дальней из них до финиша ещё не доехать, заряжаемся именно там. Просмотренные станции больше не понадобятся: вернуться к ним при движении только вперёд нельзя.
Когда в достижимой группе есть станция, с которой финиш уже достижим, это последняя необходимая зарядка. В этой группе выбираем самую раннюю станцию с station + V >= R. Предыдущие жадные шаги обеспечили максимально возможную достижимость после меньшего числа остановок, поэтому более раннего допустимого последнего места не упущено.
Сортировка O(N log N), проход O(N), память O(N). Просто брать самую дальнюю станцию до конца верно для количества, но может ухудшить координату последней.
Разбор на примере
Ввод
6 40 15 34 9 28 14 22 25
Вывод
2 25
| Шаг | Достижимые новые станции | Выбор |
|---|---|---|
| Из 0, запас 15 | 9, 14 | 14: дальше после первой зарядки |
| Из 14, запас 15 | 22, 25, 28 | 25: первая, откуда хватит до 40 |
| Из 25 | Финиш на расстоянии 15 | Зарядок больше не нужно |
Первая самая дальняя достижимая станция — 14. После неё достижимы 22, 25 и 28. Из 22 финиш 40 дальше чем на 15, а из 25 уже достижим. Поэтому последнюю зарядку делаем в 25, хотя могли бы проехать до 28. Одна зарядка не позволяет добраться: из начальных достижимых станций ни одна не находится хотя бы в 25.
Код на Python и C++
Ответ (-1, -1) — защитная ветка для недостижимого маршрута, который условием исключён. При V < R хотя бы одна зарядка обязательна.
import sys
def solve(distance, span, stations):
stations = sorted(stations)
position = count = index = 0
while position + span < distance:
begin = index
while index < len(stations) and stations[index] <= position + span:
index += 1
if begin == index:
return -1, -1
count += 1
furthest = stations[index - 1]
if furthest + span >= distance:
last = begin
while stations[last] + span < distance:
last += 1
return count, stations[last]
position = furthest
return count, position
if __name__ == '__main__':
n, distance, span, *stations = map(int, sys.stdin.buffer.read().split())
print(*solve(distance, span, stations))
<algorithm>
<iostream>
<utility>
<vector>
using namespace std;
pair<long long, long long> solve(long long distance, long long span, vector<long long> stations) {
sort(stations.begin(), stations.end());
long long position = 0, count = 0;
size_t index = 0;
while (position + span < distance) {
size_t begin = index;
while (index < stations.size() && stations[index] <= position + span)
index += 1;
if (begin == index)
return {-1, -1};
count += 1;
long long furthest = stations[index - 1];
if (furthest + span >= distance) {
size_t last = begin;
while (stations[last] + span < distance)
last += 1;
return {count, stations[last]};
}
position = furthest;
}
return {count, position};
}
int main() {
int n;
long long distance, span;
cin >> n >> distance >> span;
vector<long long> stations(n);
for (long long& station : stations)
cin >> station;
auto [count, last] = solve(distance, span, stations);
cout << count << ' ' << last << endl;
}
Типичные ошибки
- Каждый раз выбирать ближайшую
Так робот не использует запас хода и может сделать лишние зарядки. Промежуточный шаг должен быть самым дальним.
- Последнюю тоже выбрать самой дальней
Для второго критерия нужен отдельный выбор: первая достижимая станция, откуда хватает до финиша.
- Исключить точное расстояние V
Одинаково допустимы станция ровно на границе заряда и финиш ровно в V от последней зарядки.