Dado un número N que representa la distancia total en km que debe recorrer un automóvil en una sola carretera. Hay N surtidores de gasolina a una distancia de 1 km cada uno (1, 2, 3, ..N). La capacidad del depósito de combustible del coche es tal que con el depósito lleno recorre una distancia de K km. El automóvil debe detenerse obligatoriamente en M tanques de gasolina cuya distancia desde la posición inicial se da como M números enteros. La tarea es encontrar la cantidad de veces que el automóvil debe recargar su tanque, incluidas las paradas obligatorias, para completar su viaje de N km.
Ejemplos:
Entrada: N = 5, K = 2, M = 1
arr[] = {3}
Salida: 2
El coche parte de 0, con el depósito lleno, recorre 2 km y vuelve a llenar el depósito a los 2 km. El coche hace la parada obligatoria en 3 donde se vuelve a llenar el depósito. Recorre 2 km más para llegar a su destino de 5 km.
Entrada: N = 10, K = 2, M = 3
arr[] = { 6, 7, 8 }
Salida: 5
El coche parte de 0, se detiene en 2, 4 para rellenar el depósito, antes de hacer paradas obligatorias en 6, 7, 8. Recorre 2 km desde 8 km para hacer su recorrido de 10 km completo.
Enfoque : como el viaje total es de N km, mantenga un registro de la distancia recorrida hasta ahora en una variable, digamos distCovered , que se inicializará en 0. Incremente distCovered en K km hasta que distCovered sea menor que N porque K es la cantidad de distancia que el vehículo puede recorrer desde la última recarga. Además, con cada incremento, verifique si hay una bomba de gasolina obligatoria para detenerse entre descubierta y descubierta + K, en caso afirmativo, entonces descubierta será K más la última bomba de gasolina obligatoria para detenerse entre descubierta y descubierta + K. Además, mantenga contando el número de recargas realizadas para llegar al destino de N km.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program for finding the total
// number of stops for refilling to
// reach destination of N km
#include <iostream>
using namespace std;
// Function that returns the total number of
// refills made to reach the destination of N km
int countRefill(int N, int K, int M, int compulsory[])
{
int count = 0;
int i = 0;
int distCovered = 0;
// While we complete the whole journey.
while (distCovered < N) {
// If must visited petrol pump lie
// between distCovered and distCovered+K.
if (i < M && compulsory[i] <= (distCovered + K)) {
// make last mustVisited as distCovered
distCovered = compulsory[i];
// increment the index of compulsory visited.
i++;
}
// if no such must visited pump is
// there then increment distCovered by K.
else
distCovered += K;
// Counting the number of refill.
if (distCovered < N)
count++;
}
return count;
}
// Driver Code
int main()
{
int N = 10;
int K = 2;
int M = 3;
// compulsory petrol pumps to refill at
int compulsory[] = { 6, 7, 8 };
// function call that returns the answer to the problem
cout << countRefill(N, K, M, compulsory) << endl;
return 0;
}
Java
// Java program for finding the
// total number of stops for
// refilling to reach
// destination of N km
import java.io.*;
class GFG
{
;
// Function that returns the
// total number of refills made
// to reach the destination of N km
static int countRefill(int N, int K,
int M, int compulsory[])
{
int count = 0;
int i = 0;
int distCovered = 0;
// While we complete
// the whole journey.
while (distCovered < N)
{
// If must visited petrol pump lie
// between distCovered and distCovered+K.
if (i < M && compulsory[i] <=
(distCovered + K))
{
// make last mustVisited
// as distCovered
distCovered = compulsory[i];
// increment the index
// of compulsory visited.
i++;
}
// if no such must visited
// pump is there then
// increment distCovered by K.
else
distCovered += K;
// Counting the number of refill.
if (distCovered < N)
count++;
}
return count;
}
// Driver Code
public static void main (String[] args)
{
int N = 10;
int K = 2;
int M = 3;
// compulsory petrol
// pumps to refill at
int compulsory[] = { 6, 7, 8 };
// function call that returns
// the answer to the problem
System.out.println(countRefill(N, K,
M, compulsory));
}
}
// This code is contributed by anuj_67.
Python3
# Python 3 program for finding the total # number of stops for refilling to reach # destination of N km # Function that returns the total number of # refills made to reach the destination of N km def countRefill(N, K, M, compulsory): count = 0 i = 0 distCovered = 0 # While we complete the whole journey. while (distCovered < N): # If must visited petrol pump lie # between distCovered and distCovered+K. if (i < M and compulsory[i] <= (distCovered + K)): # make last mustVisited as distCovered distCovered = compulsory[i] # increment the index of # compulsory visited. i += 1 # if no such must visited pump is # there then increment distCovered by K. else: distCovered += K # Counting the number of refill. if (distCovered < N): count += 1 return count # Driver Code if __name__ == '__main__': N = 10 K = 2 M = 3 # compulsory petrol pumps to refill at compulsory = [6, 7, 8] # function call that returns the # answer to the problem print(countRefill(N, K, M, compulsory)) # This code is contributed by # Sanjit_Prasad
C#
// C# program for finding the
// total number of stops for
// refilling to reach
// destination of N km
using System;
class GFG
{
// Function that returns
// the total number of
// refills made to reach
// the destination of N km
static int countRefill(int N, int K,
int M, int []compulsory)
{
int count = 0;
int i = 0;
int distCovered = 0;
// While we complete
// the whole journey.
while (distCovered < N)
{
// If must visited petrol pump
// lie between distCovered and
// distCovered+K.
if (i < M && compulsory[i] <=
(distCovered + K))
{
// make last mustVisited
// as distCovered
distCovered = compulsory[i];
// increment the index
// of compulsory visited.
i++;
}
// if no such must visited
// pump is there then
// increment distCovered by K.
else
distCovered += K;
// Counting the number of refill.
if (distCovered < N)
count++;
}
return count;
}
// Driver Code
public static void Main ()
{
int N = 10;
int K = 2;
int M = 3;
// compulsory petrol
// pumps to refill at
int []compulsory = {6, 7, 8};
// function call that returns
// the answer to the problem
Console.WriteLine(countRefill(N, K,
M, compulsory));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program for finding the total
// number of stops for refilling to
// reach destination of N km
// Function that returns the total
// number of refills made to reach
// the destination of N km
function countRefill($N, $K, $M,
$compulsory)
{
$count = 0;
$i = 0;
$distCovered = 0;
// While we complete
// the whole journey.
while ($distCovered < $N)
{
// If must visited petrol
// pump lie between distCovered
// and distCovered + K.
if ($i < $M and $compulsory[$i] <=
($distCovered + $K))
{
// make last mustVisited
// as distCovered
$distCovered = $compulsory[$i];
// increment the index
// of compulsory visited.
$i++;
}
// if no such must visited
// pump is there then
// increment distCovered by K.
else
$distCovered += $K;
// Counting the number
// of refill.
if ($distCovered < $N)
$count++;
}
return $count;
}
// Driver Code
$N = 10;
$K = 2;
$M = 3;
// compulsory petrol
// pumps to refill at
$compulsory = array(6, 7, 8);
// function call that returns
// the answer to the problem
echo countRefill($N, $K, $M,
$compulsory) , "\n";
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program for finding the total
// number of stops for refilling to
// reach destination of N km
// Function that returns the total number of
// refills made to reach the destination of N km
function countRefill(N, K, M, compulsory)
{
var count = 0;
var i = 0;
var distCovered = 0;
// While we complete the whole journey.
while (distCovered < N) {
// If must visited petrol pump lie
// between distCovered and distCovered+K.
if (i < M && compulsory[i] <= (distCovered + K))
{
// make last mustVisited as distCovered
distCovered = compulsory[i];
// increment the index of compulsory visited.
i++;
}
// if no such must visited pump is
// there then increment distCovered by K.
else
distCovered += K;
// Counting the number of refill.
if (distCovered < N)
count++;
}
return count;
}
// Driver Code
var N = 10;
var K = 2;
var M = 3;
// compulsory petrol pumps to refill at
var compulsory = [ 6, 7, 8 ];
// function call that returns the answer to the problem
document.write( countRefill(N, K, M, compulsory));
</script>
5
Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)