Minimalna liczba tankowań

[Szemek]

Kierowca jedzie z punktu A do punktu B. Samochód jest w stanie przejechać \(\displaystyle{ K}\) kilometrów na jednym baku. Na wejściu mamy dane pozycje kolejnych stacji benzynowych \(\displaystyle{ P[1], ..., P[n-1]}\) (mierzone jako odległość od początku trasy w kilometrach; \(\displaystyle{ P[0]=0}\) to położenie punktu startowego - A, \(\displaystyle{ P[n]}\) to położenie punktu końcowego - B. Zaimplementuj możliwie optymalny algorytm, który znajduje minimalną ilość tankowań, potrzebnych do pokonania trasy lub stwierdza, że trasy nie da się przejechać.

Wystarczy sprawdzić czy różnicę odległości pomiędzy kolejnymi stacjami. Jeśli jest większa od \(\displaystyle{ K}\) wtedy trasy nie można przejechać.
Nie mam pomysłu jednak jak wybierać te stacje, dlatego będę wdzięczny za pomoc (pseudokod) w rozwiązaniu problemu.

[argv]

Mam podobne zadanie w zeszycie starym więc je wklepie a Ty dopasuj do swoich potrzeb
Używamy strategii zachłannej:

s[1..n] - stacje benzynowe (polozenia)
Długosc trasy M kilometrow
Pojemność baku P
Zakładamy że położenia są względne (od poprzedniej stacji benzynowej)

Kod: Zaznacz cały

// obliczamy odleglosci miedzy stacjami
for i:=1 to n-1 do
	s[i+1] = s[i+1] - s[i]
	
// a[1..n] - pomocnicza tab do zaznaczenia na ktorych stacjach sie zatrzymujemy
j := P;
for i:= 1 to n do
begin
	j := j - s[i];
	if j < s[i+1] then
	begin
		a[i] = 1;
		j := P;
	end
	else
		a[i] := 0
end				

Coś takiego mam w zeszycie, nie pamiętam szczegółów i nie wiem czy to jest do konca dobrze(ew. jakies szczegoły - ale raczej powinno byc), ale mam nadzieje ze idea się przyda

[Szemek]

Dzięki wielkie. Tego mi było trzeba Tutaj jest główna część rozwiązania problemu, resztę już sobie spokojnie dorobię.