Давайте разберёмся, как решить задачу. Это классическая задача о максимизации пройденного расстояния при ограниченном бюджете, ограниченной вместимости бензобака и последовательных заправках.
### Логика решения и пошаговый разбор
1. **Понимание задачи:**
- Есть несколько заправок, каждая с ценой на литр и расположением (расстоянием от начала дороги).
- Время в пути начинается в городе с бензобаком пустым.
- Можно покупать бензин на каждой заправке, чтобы ехать дальше.
- Необходимо купить бензин так, чтобы максимизировать расстояние, на которое можно уехать, при ограниченном бюджете и вместимости бака.
2. **Ключевые моменты:**
- Расстояние точек (заправок) **упорядочены по возрастанию**.
- В начале, в городе, расстояние равняется 0, там можно купить бензин.
- Бак можно заполнить только целым числом литров.
- Необходим стратегический выбор заправок для покупки бензина по более выгодной цене.
3. **Идея решения:**
- Мы можем использовать **структуру данных типа стек или приоритетную очередь** для хранения заправок, которые мы можем посетить или уже посетили.
- Алгоритм:
- Изначально мы на расстоянии 0, бак пустой, ездить ещё нельзя.
- Переходя от заправки к заправке, мы решаем, сколько бензина купить, чтобы максимально двинуться вперёд.
- Выбираем заправки с минимальной ценой для покупки бензина.
- В процессе можем "откладывать" приобретение бензина на более дешёвых заправках, чтобы не переплачивать.
4. **Подход с жадным алгоритмом и структурой данных (например, приоритетной очередью):**
- Изначально мы в точке 0, у нас бак пустой.
- Проходим по заправкам в порядке увеличения расстояния.
- На каждом шаге:
- Расстояние до следующей заправки.
- Вычисляем, сколько бензина нужно, чтобы доехать до следующей заправки.
- Если не хватает бензина, используем доступные заправки с минимальной ценой (храним заправки в приоритетной очереди по ценам).
- В процессе покупаем бензин по наименьшей цене и расходуем по мере движения.
- В итоге, максимальное расстояние — это позиция последней достигнутой заправки или узла, на который можно добраться.
---
### Детальный пример реализации на Python
```python
import heapq
def max_distance(n, B, C, gas_stations):
# Добавляем начальную точку (город) без цены (условие)
gas_stations = [(0, 0)] + gas_stations
# Изначально бензина 0, позиция 0
current_position = 0
petrol = 0
total_cost = 0
max_distance_reached = 0
# Используем min-heap для хранения заправок по цене
min_heap = []
for i in range(1, n + 1):
x_i, p_i = gas_stations[i]
# Расстояние до следующей заправки
dist = x_i - current_position
# Проверяем, можем ли мы проехать это расстояние с текущим бензином
while petrol < dist:
# Не хватает бензина для достижения следующей заправки
if not min_heap:
# Нет более дешевых заправок для покупки бензина
return current_position + petrol
# Покупаем бензин по самой низкой цене из уже посещённых заправок
price = heapq.heappop(min_heap)
# Максимально можем купить, чтобы добраться
max_buy = min(C - petrol, (dist - petrol))
# Ограничение по бюджету
# Вычисляем сколько фантиков затратим
cost = max_buy * price
if total_cost + cost > B:
max_buy_possible = (B - total_cost) // price
petrol += max_buy_possible
total_cost += max_buy_possible * price
break
else:
petrol += max_buy
total_cost += cost
# Теперь мы можем доехать
petrol -= dist
current_position = x_i
max_distance_reached = current_position
# Добавляем заправку в структуру, чтобы использовать при дальнейшем движении
heapq.heappush(min_heap, p_i)
# Достигли последней заправки, максимум - текущая позиция
return max_distance_reached
```
### Объяснение кода:
- Мы начинаем с добавления начальной точки (0, цена 0) — город.
- Проходим по заправкам в порядке появления.
- Расчитываем, сколько бензина нужно, чтобы дойти до следующей.
- Используем минимум-кучу, чтобы всегда покупать бензин по самой низкой цене.
- В процессе покупок учитываем ограничения по бюджету и вместимости бака.
- После прохождения всех заправок возвращаем расстояние, на которое смогли доехать.
---
### Итог:
- Этот алгоритм жадный, использует структуру данных — приоритетную очередь для выбора самых выгодных заправок.
- По времени сложность — \( O(n \log n) \), что приемлемо для \( n \leq 10^5 \).
Если у вас есть конкретные параметры для тестирования или дополнительные вопросы, я помогу вам их решить!
