Условие задачи

Программист едет по шоссе из Москвы в Новгород. У него есть карта с указанием всех бензоколонок и расстояний до них от Москвы. Известно расстояние $S$, которое может проехать машина с полностью заправленным баком. Требуется выяснить, на каких бензоколонках нужно заправляться, чтобы количество заправок было минимально. В начале пути бак полон. Расстояние от Москвы до Новгорода = $L$ . Если добраться до Новгорода невозможно, выведите $-1$.

---

Решение

Отсортируем расстояния до станций по возрастанию, мы можем так сделать, потому что порядок станций не важен. Если до ближайшей станции расстояние больше чем $S$, ответ $-1$, иначе начинаем перебирать станции.

Изначальный путь установим равным $S$. Если расстояние до станции больше текущего пути и текущий путь < $L$, тогда мы остановились на предыдущей станции, добавляем в счётчик ответа $1$ и увеличиваем путь на расстояние до предыдущей станции.

Продолжаем перебирать станции, пока они не закончатся. Если после перебора всех станций путь < $L$, тогда ответ $-1$.

---

Сложность

Сложность алгоритма - $O(n) + n*log_2 n$, где $n$ - количество станций.

---

Псевдокод

Аннотация:
stations - список расстояний до каждой заправки
s - максимальное расстояние, которое может проехать автомобиль на полном баке
l - общее расстояние, которое нужно проехать

Функция_вычисления(stations, s, l)
    путь <- s
    правильные_станции <- пустой список

    сортировать станции по возрастанию

    если s < путь до 1-ой станции
        то вернуть -1

    для станции в stations
        если станция > пути & путь < l
            то добавляем предыдущую станцию в правильные_станции
               путь <- предыдущая станция + s
               
    если путь < l 
        то вернуть -1
        
    вернуть длину списка правильные_станции

---

Реализация на Python

Аннотация:
count_gas_stations - функция для вычисления минимального количества заправок
gas_stations - список расстояний до каждой заправки
s - максимальное расстояние, которое может проехать автомобиль на полном баке
l - общее расстояние, которое нужно проехать
way - переменная для отслеживания текущего пройденного расстояния
right_stations - список выбранных заправок

def count_gas_stations(gas_stations, s, l):  
    way = s  
    right_stations = list()  
    gas_stations.append(l)  
    gas_stations.sort()  
    
    for station in range(len(gas_stations)):  
        if gas_stations[0] > s:  
            return -1  
            
        if gas_stations[station] > way and way < l:  
            right_stations.append(gas_stations[station - 1])  
            way = gas_stations[station - 1] + s
            
    if way < l:  
        return -1  
        
    return len(right_stations)

---

Олимпиадная реализация на C++

Аннотация:
k_stat - функция для вычисления минимального количества заправок.
stat - вектор расстояний до каждой заправки.
s - максимальное расстояние, которое может проехать автомобиль на полном баке.
l - общее расстояние, которое нужно проехать.
way - переменная для отслеживания текущего пройденного расстояния.
ans - вектор выбранных заправок.

int k_stat(vector<int> stat, int s, int l){
    int way = s;
    vector<int> ans;
    stat.push_back(l);
    sort(stat.begin(), stat.end());
    
    for (int i = 1; i < stat.size(); i++){
        if (stat[0] > s) {return -1;}
        
        if (stat[i] > way and way < l){
            ans.push_back(stat[i - 1]);  
            way = stat[i - 1] + s;
        }
    };
    
    if (way < l) {return -1;}
    
    return ans.size();
}

---

Продуктовая реализация на C++

Аннотация:
count_gas_stations - функция для вычисления минимального количества заправок.
gas_stations - вектор расстояний до каждой заправки.
step - максимальное расстояние, которое может проехать автомобиль на полном баке.
all_way - общее расстояние, которое нужно проехать.
way - переменная для отслеживания текущего пройденного расстояния.
right_stations - вектор выбранных заправок.

int count_gas_stations(vector<int> gas_stations, int step, int all_way) {
    int way = step;
    vector<int> right_stations;
    gas_stations.push_back(all_way);
    int first_station = gas_stations[0];
    
    if (first_station > step) { return -1; }
    
    sort(gas_stations.begin(), gas_stations.end());
    
    for (int station = 1; station < gas_stations.size(); station++) {
        if (gas_stations[station] > way and way < all_way) {
            right_stations.push_back(gas_stations[station - 1]);
            way = gas_stations[station - 1] + step;
        }
    };
    
    if (way < all_way) { return -1; }
    
    return right_stations.size();
}