Supongamos que hay un círculo. Hay n surtidores de gasolina en ese círculo. Se le dan dos conjuntos de datos.
- La cantidad de gasolina que tiene cada surtidor de gasolina.
- Distancia desde ese surtidor de gasolina hasta el siguiente surtidor de gasolina.
Calcula el primer punto desde donde un camión podrá completar el círculo (El camión se detendrá en cada surtidor de gasolina y tiene capacidad infinita). La complejidad de tiempo esperada es O(n). Suponga que para 1 litro de gasolina, el camión puede recorrer 1 unidad de distancia.
Por ejemplo, suponga que hay 4 surtidores de gasolina con la cantidad de gasolina y la distancia al siguiente par de valores del surtidor de gasolina como {4, 6}, {6, 5}, {7, 3} y {4, 5}. El primer punto desde donde el camión puede realizar un recorrido circular es el 2º surtidor de gasolina. La salida debe ser «inicio = 1» (índice de la 2ª bomba de gasolina).
Una solución simple es considerar todos los surtidores de gasolina como punto de partida y ver si hay un recorrido posible. Si encontramos un punto de partida con una solución factible, devolvemos ese punto de partida. La complejidad de tiempo del peor de los casos de esta solución es O (n ^ 2).
Un enfoque eficiente es utilizar una Cola para almacenar el recorrido actual. Primero ponemos en cola el primer surtidor de gasolina en la cola, seguimos poniendo en cola los surtidores de gasolina hasta que completamos el recorrido o la cantidad actual de gasolina se vuelve negativa. Si la cantidad se vuelve negativa, seguimos sacando de la cola los surtidores de gasolina hasta que la cola se vacía.
En lugar de crear una cola separada, usamos la array dada como una cola. Mantenemos dos variables de índice, inicio y fin, que representan la parte trasera y delantera de la cola.
La imagen de abajo es una ejecución en seco del enfoque anterior:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find circular tour for a truck
#include <bits/stdc++.h>
using namespace std;
// A petrol pump has petrol and distance to next petrol pump
class petrolPump
{
public:
int petrol;
int distance;
};
// The function returns starting point if there is a possible solution,
// otherwise returns -1
int printTour(petrolPump arr[], int n)
{
// Consider first petrol pump as a starting point
int start = 0;
int end = 1;
int curr_petrol = arr[start].petrol - arr[start].distance;
/* Run a loop while all petrol pumps are not visited.
And we have reached first petrol pump again with 0 or more petrol */
while (end != start || curr_petrol < 0)
{
// If current amount of petrol in truck becomes less than 0, then
// remove the starting petrol pump from tour
while (curr_petrol < 0 && start != end)
{
// Remove starting petrol pump. Change start
curr_petrol -= arr[start].petrol - arr[start].distance;
start = (start + 1) % n;
// If 0 is being considered as start again, then there is no
// possible solution
if (start == 0)
return -1;
}
// Add a petrol pump to current tour
curr_petrol += arr[end].petrol - arr[end].distance;
end = (end + 1) % n;
}
// Return starting point
return start;
}
// Driver code
int main()
{
petrolPump arr[] = {{6, 4}, {3, 6}, {7, 3}};
int n = sizeof(arr)/sizeof(arr[0]);
int start = printTour(arr, n);
(start == -1)? cout<<"No solution": cout<<"Start = "<<start;
return 0;
}
// This code is contributed by rathbhupendra
C
// C program to find circular tour for a truck
#include <stdio.h>
// A petrol pump has petrol and distance to next petrol pump
struct petrolPump
{
int petrol;
int distance;
};
// The function returns starting point if there is a possible solution,
// otherwise returns -1
int printTour(struct petrolPump arr[], int n)
{
// Consider first petrol pump as a starting point
int start = 0;
int end = 1;
int curr_petrol = arr[start].petrol - arr[start].distance;
/* Run a loop while all petrol pumps are not visited.
And we have reached first petrol pump again with 0 or more petrol */
while (end != start || curr_petrol < 0)
{
// If current amount of petrol in truck becomes less than 0, then
// remove the starting petrol pump from tour
while (curr_petrol < 0 && start != end)
{
// Remove starting petrol pump. Change start
curr_petrol -= arr[start].petrol - arr[start].distance;
start = (start + 1)%n;
// If 0 is being considered as start again, then there is no
// possible solution
if (start == 0)
return -1;
}
// Add a petrol pump to current tour
curr_petrol += arr[end].petrol - arr[end].distance;
end = (end + 1)%n;
}
// Return starting point
return start;
}
// Driver program to test above functions
int main()
{
struct petrolPump arr[] = {{6, 4}, {3, 6}, {7, 3}};
int n = sizeof(arr)/sizeof(arr[0]);
int start = printTour(arr, n);
(start == -1)? printf("No solution"): printf("Start = %d", start);
return 0;
}
Java
//Java program to find circular tour for a truck
public class Petrol
{
// A petrol pump has petrol and distance to next petrol pump
static class petrolPump
{
int petrol;
int distance;
// constructor
public petrolPump(int petrol, int distance)
{
this.petrol = petrol;
this.distance = distance;
}
}
// The function returns starting point if there is a possible solution,
// otherwise returns -1
static int printTour(petrolPump arr[], int n)
{
int start = 0;
int end = 1;
int curr_petrol = arr[start].petrol - arr[start].distance;
// If current amount of petrol in truck becomes less than 0, then
// remove the starting petrol pump from tour
while(end != start || curr_petrol < 0)
{
// If current amount of petrol in truck becomes less than 0, then
// remove the starting petrol pump from tour
while(curr_petrol < 0 && start != end)
{
// Remove starting petrol pump. Change start
curr_petrol -= arr[start].petrol - arr[start].distance;
start = (start + 1) % n;
// If 0 is being considered as start again, then there is no
// possible solution
if(start == 0)
return -1;
}
// Add a petrol pump to current tour
curr_petrol += arr[end].petrol - arr[end].distance;
end = (end + 1)%n;
}
// Return starting point
return start;
}
// Driver program to test above functions
public static void main(String[] args)
{
petrolPump[] arr = {new petrolPump(6, 4),
new petrolPump(3, 6),
new petrolPump(7, 3)};
int start = printTour(arr, arr.length);
System.out.println(start == -1 ? "No Solution" : "Start = " + start);
}
}
//This code is contributed by Sumit Ghosh
Python
# Python program to find circular tour for a truck
# In this approach we will start the tour from the first petrol pump
# then while moving to the next pumps in the loop we will store the cumulative
# information that whether we have a deficit of petrol at the current pump or not
# If there is a deficit then we will add it to the deficit value calculated
# till the previous petrol pump and then update the starting point to the next pump
# and reset the petrol available in the truck as 0
# This function return starting point if there is a possible
# solution otherwise returns -1
def printTour(arr,n):
# Consider first petrol pump as starting point
start = 0
# These two variable will keep tracking if there is
# surplus(s) or deficit(d) of petrol in the truck
s = 0 # petrol available the truck till now
d = 0 # deficit of petrol till visiting this petrol pump
# Start from the first petrol pump and complete one loop
# of visiting all the petrol pumps and keep updating s and d at each pump
for i in range(n):
s += arr[i][0] - arr[i][1]
if s < 0: # the truck has a deficit of petrol
start = i+1 # change the starting point
d += s # storing the deficit of petrol till current petrol pump
s = 0 # starting again from new station
# when we reach first petrol pump again and sum of the petrol available at the truck
# and the petrol deficit till now is 0 or more petrol then return the starting point
# else return -1
return start if (s+d)>=0 else -1
# Driver program to test above function
arr = [[6,4], [3,6], [7,3]]
start = printTour(arr,3)
if start == -1:
print("No Solution Possible !!!")
else:
print("start = {}".format(start))
# This code is contributed by Antara Das(anny)
C#
// C# program to find circular
// tour for a truck
using System;
class GFG
{
// A petrol pump has petrol and
// distance to next petrol pump
public class petrolPump
{
public int petrol;
public int distance;
// constructor
public petrolPump(int petrol,
int distance)
{
this.petrol = petrol;
this.distance = distance;
}
}
// The function returns starting point
// if there is a possible solution,
// otherwise returns -1
public static int printTour(petrolPump[] arr,
int n)
{
int start = 0;
int end = 1;
int curr_petrol = arr[start].petrol -
arr[start].distance;
// If current amount of petrol in
// truck becomes less than 0, then
// remove the starting petrol pump from tour
while (end != start || curr_petrol < 0)
{
// If current amount of petrol in
// truck becomes less than 0, then
// remove the starting petrol pump from tour
while (curr_petrol < 0 && start != end)
{
// Remove starting petrol pump.
// Change start
curr_petrol -= arr[start].petrol -
arr[start].distance;
start = (start + 1) % n;
// If 0 is being considered as
// start again, then there is no
// possible solution
if (start == 0)
{
return -1;
}
}
// Add a petrol pump to current tour
curr_petrol += arr[end].petrol -
arr[end].distance;
end = (end + 1) % n;
}
// Return starting point
return start;
}
// Driver Code
public static void Main(string[] args)
{
petrolPump[] arr = new petrolPump[]
{
new petrolPump(6, 4),
new petrolPump(3, 6),
new petrolPump(7, 3)
};
int start = printTour(arr, arr.Length);
Console.WriteLine(start == -1 ? "No Solution" :
"Start = " + start);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// JavaScript program to find circular tour for a truck
// A petrol pump has petrol and distance to next petrol pump
class petrolPump {
constructor(petrol, distance) {
this.petrol = petrol;
this.distance = distance;
}
};
// The function returns starting point if there is a possible solution,
// otherwise returns -1
const printTour = (arr, n) => {
// Consider first petrol pump as a starting point
let start = 0;
let end = 1;
let curr_petrol = arr[start].petrol - arr[start].distance;
/* Run a loop while all petrol pumps are not visited.
And we have reached first petrol pump again with 0 or more petrol */
while (end != start || curr_petrol < 0) {
// If current amount of petrol in truck becomes less than 0, then
// remove the starting petrol pump from tour
while (curr_petrol < 0 && start != end) {
// Remove starting petrol pump. Change start
curr_petrol -= arr[start].petrol - arr[start].distance;
start = (start + 1) % n;
// If 0 is being considered as start again, then there is no
// possible solution
if (start == 0)
return -1;
}
// Add a petrol pump to current tour
curr_petrol += arr[end].petrol - arr[end].distance;
end = (end + 1) % n;
}
// Return starting point
return start;
}
// Driver code
let arr = [new petrolPump(6, 4), new petrolPump(3, 6), new petrolPump(7, 3)];
let n = arr.length;
let start = printTour(arr, n);
(start == -1) ? document.write("No solution") : document.write(`Start = ${start}`);
// This code is contributed by rakeshsahni
</script>
Producción
Start = 2
Complejidad de tiempo: estamos visitando cada bomba de gasolina exactamente una vez, por lo tanto, la complejidad de tiempo es O (n)
Espacio Auxiliar: O(1)
Otra solución eficaz puede ser encontrar el primer surtidor de gasolina en el que la cantidad de gasolina sea mayor o igual a la distancia a recorrer para llegar al siguiente surtidor de gasolina. Ahora marcamos ese surtidor de gasolina como inicio y ahora comprobamos si podemos terminar el recorrido hacia el punto final. Si en medio, en cualquier surtidor de gasolina, la cantidad de gasolina es menor que la distancia a recorrer para llegar al siguiente surtidor de gasolina, entonces podemos decir que no podemos completar el recorrido circular desde el principio . De nuevo tratamos de averiguar el siguiente punto desde donde podemos iniciar nuestro viaje, es decir, el siguiente surtidor de gasolina donde la cantidad de gasolina es mayor o igual a la distancia a recorrer y lo marcamos como inicio .. No necesitamos mirar ningún surtidor de gasolina entre el surtidor de gasolina inicial marcado como inicio y el nuevo inicio , ya que sabemos que no podemos completar el viaje si comenzamos desde cualquier surtidor de gasolina intermedio porque eventualmente llegaremos a un punto donde la cantidad de gasolina es menor que la distancia. Ahora repetimos el proceso hasta llegar al último surtidor de gasolina y actualizamos nuestro inicio cuando sea necesario. Después de llegar a nuestro último surtidor de gasolina, intentamos llegar a nuestro primer surtidor de gasolina desde el último y digamos que tenemos una cantidad restante de gasolina como curr_petrol . Ahora empezamos de nuevo a viajar desde el primer surtidor de gasolina y aprovechamos nuestro curr_petrol e intentamos llegar al inicio. Si podemos llegar al inicio , entonces podemos concluir que el inicio puede ser nuestro punto de partida. Ahora es posible que se pregunte, incluso después de llegar al final de la array, por qué no estamos haciendo ningún recorrido circular y, después de llegar al final, estamos concluyendo el resultado. El concepto principal es que: –
Supongamos que comenzamos en la bomba 0 y avanzamos y en el medio tenemos combustible negativo, por lo que reiniciaremos nuestro viaje desde la posición media. Ahora supongamos que después de llegar al final tenemos algo de combustible en el tanque. Estamos diciendo que la posición media será la posición inicial. Pero, ¿por qué no volvemos al elemento medio (desde donde comenzamos nuestro viaje) desde el final para comprobar si es posible hacer un recorrido circular o no? Es porque ya hemos comprobado anteriormente que es posible llegar desde el índice 0 hasta el medio. Por lo tanto, no es necesario verificar la parte restante del recorrido circular, ya que siempre será un recorrido válido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find circular tour for a truck
#include <bits/stdc++.h>
using namespace std;
// A petrol pump has petrol and distance to next petrol pump
class petrolPump {
public:
int petrol;
int distance;
};
// The function returns starting point if there is a
// possible solution, otherwise returns -1
int printTour(petrolPump arr[], int n)
{
int start;
for (int i = 0; i < n; i++) {
// Identify the first petrol pump from where we
// might get a full circular tour
if (arr[i].petrol >= arr[i].distance) {
start = i;
break;
}
}
// To store the excess petrol
int curr_petrol = 0;
int i;
for (i = start; i < n;) {
curr_petrol += (arr[i].petrol - arr[i].distance);
// If at any point remaining petrol is less than 0,
// it means that we cannot start our journey from
// current start
if (curr_petrol < 0) {
// We move to the next petrol pump
i++;
// We try to identify the next petrol pump from
// where we might get a full circular tour
for (; i < n; i++) {
if (arr[i].petrol >= arr[i].distance) {
start = i;
// Reset rem_petrol
curr_petrol = 0;
break;
}
}
}
else {
// Move to the next petrolpump if curr_petrol is
// >= 0
i++;
}
}
// If remaining petrol is less than 0 while we reach the
// first petrol pump, it means no circular tour is
// possible
if (curr_petrol < 0) {
return -1;
}
for (int j = 0; j < start; j++) {
curr_petrol += (arr[j].petrol - arr[j].distance);
// If remaining petrol is less than 0 at any point
// before we reach initial start, it means no
// circular tour is possible
if (curr_petrol < 0) {
return -1;
}
}
// If we have successfully reached intial_start, it
// means can get a circular tour from final_start, hence
// return it
return start;
}
// Driver code
int main()
{
petrolPump arr[] = { { 6, 4 }, { 3, 6 }, { 7, 3 } };
int n = sizeof(arr) / sizeof(arr[0]);
int start = printTour(arr, n);
(start == -1) ? cout << "No solution"
: cout << "Start = " << start;
return 0;
}
// This code is contributed by supratik_mitra
C
// C program to find circular tour for a truck
#include <stdio.h>
// A petrol pump has petrol and distance to next petrol pump
struct petrolPump {
int petrol;
int distance;
};
// The function returns starting point if there is a
// possible solution, otherwise returns -1
int printTour(struct petrolPump arr[], int n)
{
int start;
for (int i = 0; i < n; i++) {
// Identify the first petrol pump from where we
// might get a full circular tour
if (arr[i].petrol >= arr[i].distance) {
start = i;
break;
}
}
// To store the excess petrol
int curr_petrol = 0;
int i;
for (i = start; i < n;) {
curr_petrol += (arr[i].petrol - arr[i].distance);
// If at any point remaining petrol is less than 0,
// it means that we cannot start our journey from
// current start
if (curr_petrol < 0) {
// We move to the next petrol pump
i++;
// We try to identify the next petrol pump from
// where we might get a full circular tour
for (; i < n; i++) {
if (arr[i].petrol >= arr[i].distance) {
start = i;
// Reset rem_petrol
curr_petrol = 0;
break;
}
}
}
else
{
// Move to the next petrolpump if curr_petrol is
// >= 0
i++;
}
}
// If remaining petrol is less than 0 while we reach the
// first petrol pump, it means no circular tour is
// possible
if (curr_petrol < 0) {
return -1;
}
for (int j = 0; j < start; j++) {
curr_petrol += (arr[j].petrol - arr[j].distance);
// If remaining petrol is less than 0 at any point
// before we reach initial start, it means no
// circular tour is possible
if (curr_petrol < 0) {
return -1;
}
}
// If we have successfully reached intial_start, it
// means can get a circular tour from final_start, hence
// return it
return start;
}
// Driver code
int main()
{
struct petrolPump arr[]
= { { 6, 4 }, { 3, 6 }, { 7, 3 } };
int n = sizeof(arr) / sizeof(arr[0]);
int start = printTour(arr, n);
(start == -1) ? printf("No solution")
: printf("Start = %d", start);
return 0;
}
// This code is contributed by jainlovely450
Java
// Java program to find circular tour for a truck
public class Circular
{
// A petrol pump has petrol and distance to next petrol
// pump
static class petrolPump {
int petrol;
int distance;
public petrolPump(int petrol, int distance)
{
this.petrol = petrol;
this.distance = distance;
}
}
// The function returns starting point if there is a
// possible solution, otherwise returns -1
static int printTour(petrolPump arr[], int n)
{
int start = 0;
for (int i = 0; i < n; i++) {
// Identify the first petrol pump from where we
// might get a full circular tour
if (arr[i].petrol >= arr[i].distance) {
start = i;
break;
}
}
// To store the excess petrol
int curr_petrol = 0;
int i;
for (i = start; i < n;) {
curr_petrol
+= (arr[i].petrol - arr[i].distance);
// If at any point remaining petrol is less than
// 0, it means that we cannot start our journey
// from current start
if (curr_petrol < 0) {
// We move to the next petrol pump
i++;
// We try to identify the next petrol pump
// from where we might get a full circular
// tour
for (; i < n; i++) {
if (arr[i].petrol >= arr[i].distance) {
start = i;
// Reset rem_petrol
curr_petrol = 0;
break;
}
}
}
else {
// Move to the next petrolpump if
// curr_petrol is
// >= 0
i++;
}
}
// If remaining petrol is less than 0 while we reach
// the first petrol pump, it means no circular tour
// is possible
if (curr_petrol < 0) {
return -1;
}
for (int j = 0; j < start; j++) {
curr_petrol
+= (arr[j].petrol - arr[j].distance);
// If remaining petrol is less than 0 at any
// point before we reach initial start, it means
// no circular tour is possible
if (curr_petrol < 0) {
return -1;
}
}
// If we have successfully reached intial_start, it
// means can get a circular tour from final_start,
// hence return it
return start;
}
// Driver code
public static void main(String[] args)
{
petrolPump arr[]
= { new petrolPump(6, 4), new petrolPump(3, 6),
new petrolPump(7, 3) };
int n = arr.length;
int start = printTour(arr, n);
System.out.println(start == -1
? "No solution"
: "Start = " + start);
}
}
// This code is contributed by jainlovely450
Python3
# Python program to find circular tour for a truck
# A petrol pump has petrol and distance to next petrol pump
class petrolPump:
def __init__(self, petrol, distance):
self.petrol = petrol
self.distance = distance
# The function returns starting point if there is a
# possible solution, otherwise returns -1
def printTour(arr, n):
start = 0
for i in range(n):
# Identify the first petrol pump from where we
# might get a full circular tour
if arr[i].petrol >= arr[i].distance:
start = i
break
# To store the excess petrol
curr_petrol = 0
for i in range(start, n):
curr_petrol += (arr[i].petrol - arr[i].distance)
# If at any point remaining petrol is less than 0,
# it means that we cannot start our journey from
# current start
if(curr_petrol < 0):
# We move to the next petrol pump
i += 1
# We try to identify the next petrol pump from
# where we might get a full circular tour
while(i < n):
if(arr[i].petrol >= arr[i].distance):
start = i
# Reset rem_petrol
curr_petrol = 0
break
i += 1
else:
# Move to the next petrolpump if curr_petrol is
# >= 0
i += 1
''' If remaining petrol is less than 0 while we reach the
first petrol pump, it means no circular tour is
possible '''
if(curr_petrol < 0):
return -1
for i in range(start):
curr_petrol += (arr[i].petrol - arr[i].distance)
''' If remaining petrol is less than 0 at any point
before we reach initial start, it means no
circular tour is possible '''
if(curr_petrol < 0):
return -1
''' If we have successfully reached intial_start, it
means can get a circular tour from final_start, hence
return it '''
return start
# Driver code
arr = [petrolPump(6, 4), petrolPump(3, 6), petrolPump(7, 3)]
start = printTour(arr, len(arr))
if start == -1:
print("No solution")
else:
print("Start = {}".format(start))
# This code is contributed by jainlovely450
C#
using System;
// C# program to find circular tour for a truck
public class Circular {
// A petrol pump has petrol and distance to next petrol
// pump
public class petrolPump {
public int petrol;
public int distance;
public petrolPump(int petrol, int distance) {
this.petrol = petrol;
this.distance = distance;
}
}
// The function returns starting point if there is a
// possible solution, otherwise returns -1
static int printTour(petrolPump []arr, int n) {
int start = 0;
int i;
for ( i = 0; i < n; i++)
{
// Identify the first petrol pump from where we
// might get a full circular tour
if (arr[i].petrol >= arr[i].distance) {
start = i;
break;
}
}
// To store the excess petrol
int curr_petrol = 0;
for (i = start; i < n;) {
curr_petrol += (arr[i].petrol - arr[i].distance);
// If at any point remaining petrol is less than
// 0, it means that we cannot start our journey
// from current start
if (curr_petrol < 0) {
// We move to the next petrol pump
i++;
// We try to identify the next petrol pump
// from where we might get a full circular
// tour
for (; i < n; i++) {
if (arr[i].petrol >= arr[i].distance) {
start = i;
// Reset rem_petrol
curr_petrol = 0;
break;
}
}
}
else {
// Move to the next petrolpump if
// curr_petrol is
// >= 0
i++;
}
}
// If remaining petrol is less than 0 while we reach
// the first petrol pump, it means no circular tour
// is possible
if (curr_petrol < 0) {
return -1;
}
for (int j = 0; j < start; j++) {
curr_petrol += (arr[j].petrol - arr[j].distance);
// If remaining petrol is less than 0 at any
// point before we reach initial start, it means
// no circular tour is possible
if (curr_petrol < 0) {
return -1;
}
}
// If we have successfully reached intial_start, it
// means can get a circular tour from final_start,
// hence return it
return start;
}
// Driver code
public static void Main(String[] args) {
petrolPump []arr = { new petrolPump(6, 4),
new petrolPump(3, 6),
new petrolPump(7, 3) };
int n = arr.Length;
int start = printTour(arr, n);
Console.WriteLine(start == -1 ? "No solution" : "Start = " + start);
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// JavaScript program to find circular tour for a truck
// A petrol pump has petrol and distance to next petrol pump
class petrolPump {
constructor(petrol, distance) {
this.petrol = petrol;
this.distance = distance;
}
};
// The function returns starting point if there is a
// possible solution, otherwise returns -1
const printTour = (arr, n) => {
let start;
for (let i = 0; i < n; i++)
{
// Identify the first petrol pump from where we
// might get a full circular tour
if (arr[i].petrol >= arr[i].distance) {
start = i;
break;
}
}
// To store the excess petrol
let curr_petrol = 0;
let i;
for (i = start; i < n;)
{
curr_petrol += (arr[i].petrol - arr[i].distance);
// If at any point remaining petrol is less than 0,
// it means that we cannot start our journey from
// current start
if (curr_petrol < 0) {
// We move to the next petrol pump
i++;
// We try to identify the next petrol pump from
// where we might get a full circular tour
for (; i < n; i++) {
if (arr[i].petrol >= arr[i].distance) {
start = i;
// Reset rem_petrol
curr_petrol = 0;
break;
}
}
}
else {
// Move to the next petrolpump if curr_petrol is
// >= 0
i++;
}
}
// If remaining petrol is less than 0 while we reach the
// first petrol pump, it means no circular tour is
// possible
if (curr_petrol < 0) {
return -1;
}
for (let j = 0; j < start; j++) {
curr_petrol += (arr[j].petrol - arr[j].distance);
// If remaining petrol is less than 0 at any point
// before we reach initial start, it means no
// circular tour is possible
if (curr_petrol < 0) {
return -1;
}
}
// If we have successfully reached intial_start, it
// means can get a circular tour from final_start, hence
// return it
return start;
}
// Driver code
let arr = [new petrolPump(6, 4), new petrolPump(3, 6), new petrolPump(7, 3)];
let n = arr.length;
let start = printTour(arr, n);
(start == -1) ? document.write("No solution") : document.write(`Start = ${start}`);
// This code is contributed by rakeshsahni
</script>
Producción
Start = 2
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Otro enfoque más simple es almacenar el valor de la capacidad en alguna variable siempre que la capacidad sea menor que cero.
En este caso, debe recorrer la array solo una vez en comparación con el método anterior que atraviesa cada índice dos veces.
Aquí está la implementación de la idea anterior: –
C++
// C++ program to find circular tour for a truck
#include <bits/stdc++.h>
using namespace std;
// A petrol pump has petrol and distance to next petrol pump
class petrolPump {
public:
int petrol;
int distance;
};
// The function returns starting point if there is a
// possible solution, otherwise returns -1
int printTour(petrolPump p[], int n)
{
// deficit is used to store the value of the capacity as
// soon as the value of capacity becomes negative so as
// not to traverse the array twice in order to get the
// solution
int start = 0, deficit = 0;
int capacity = 0;
for (int i = 0; i < n; i++) {
capacity += p[i].petrol - p[i].distance;
if (capacity < 0) {
// If this particular step is not done then the
// between steps would be redundant
start = i + 1;
deficit += capacity;
capacity = 0;
}
}
return (capacity + deficit >= 0) ? start : -1;
}
// Driver code
int main()
{
petrolPump arr[] = { { 6, 4 }, { 3, 6 }, { 7, 3 } };
int n = sizeof(arr) / sizeof(arr[0]);
int start = printTour(arr, n);
(start == -1) ? cout << "No solution"
: cout << "Start = " << start;
return 0;
}
// This code is contributed by aditya kumar
Java
// Java program to find circular tour for a truck
import java.util.*;
class GFG {
// A petrol pump has petrol and distance to next petrol pump
static class petrolPump {
int petrol;
int distance;
petrolPump(int a, int b) {
this.petrol = a;
this.distance = b;
}
};
// The function returns starting point if there is a
// possible solution, otherwise returns -1
static int printTour(petrolPump p[], int n)
{
// deficit is used to store the value of the capacity as
// soon as the value of capacity becomes negative so as
// not to traverse the array twice in order to get the
// solution
int start = 0, deficit = 0;
int capacity = 0;
for (int i = 0; i < n; i++) {
capacity += p[i].petrol - p[i].distance;
if (capacity < 0) {
// If this particular step is not done then the
// between steps would be redundant
start = i + 1;
deficit += capacity;
capacity = 0;
}
}
return (capacity + deficit >= 0) ? start : -1;
}
// Driver code
public static void main(String[] args) {
petrolPump arr[] = { new petrolPump(6, 4),
new petrolPump(3, 6),
new petrolPump(7, 3) };
int n = arr.length;
int start = printTour(arr, n);
if (start == -1)
System.out.print("No solution");
else
System.out.print("Start = " + start);
}
}
// This code is contributed by umadevi9616
Python3
# Python program to find circular tour for a truck
# A petrol pump has petrol and distance to next petrol pump
class petrolPump:
def __init__(self,a, b):
self.petrol = a;
self.distance = b;
# The function returns starting point if there is a
# possible solution, otherwise returns -1
def printTour( p, n):
# deficit is used to store the value of the capacity as
# soon as the value of capacity becomes negative so as
# not to traverse the array twice in order to get the
# solution
start = 0;
deficit = 0;
capacity = 0;
for i in range(n):
capacity += p[i].petrol - p[i].distance;
if (capacity < 0):
# If this particular step is not done then the
# between steps would be redundant
start = i + 1;
deficit += capacity;
capacity = 0;
if(capacity + deficit >= 0):
return start;
else:
return -1;
# Driver code
if __name__ == '__main__':
arr = [petrolPump(6, 4),petrolPump(3, 6),petrolPump(7, 3)] ;
n = len(arr);
start = printTour(arr, n);
if (start == -1):
print("No solution");
else:
print("Start = " , start);
# This code is contributed by Rajput-Ji
C#
// C# program to find circular tour for a truck
using System;
public class GFG {
// A petrol pump has petrol and distance to next petrol pump
public class petrolPump {
public int petrol;
public int distance;
public petrolPump(int a, int b) {
this.petrol = a;
this.distance = b;
}
};
// The function returns starting point if there is a
// possible solution, otherwise returns -1
static int printTour(petrolPump []p, int n) {
// deficit is used to store the value of the capacity as
// soon as the value of capacity becomes negative so as
// not to traverse the array twice in order to get the
// solution
int start = 0, deficit = 0;
int capacity = 0;
for (int i = 0; i < n; i++) {
capacity += p[i].petrol - p[i].distance;
if (capacity < 0)
{
// If this particular step is not done then the
// between steps would be redundant
start = i + 1;
deficit += capacity;
capacity = 0;
}
}
return (capacity + deficit >= 0) ? start : -1;
}
// Driver code
public static void Main(String[] args)
{
petrolPump []arr = { new petrolPump(6, 4),
new petrolPump(3, 6),
new petrolPump(7, 3) };
int n = arr.Length;
int start = printTour(arr, n);
if (start == -1)
Console.Write("No solution");
else
Console.Write("Start = " + start);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript program to find circular tour for a truck
// A petrol pump has petrol and distance to next petrol pump
class petrolPump {
constructor(a , b) {
this.petrol = a;
this.distance = b;
}
}
// The function returns starting point if there is a
// possible solution, otherwise returns -1
function printTour( p , n) {
// deficit is used to store the value of the capacity as
// soon as the value of capacity becomes negative so as
// not to traverse the array twice in order to get the
// solution
var start = 0, deficit = 0;
var capacity = 0;
for (i = 0; i < n; i++) {
capacity += p[i].petrol - p[i].distance;
if (capacity < 0) {
// If this particular step is not done then the
// between steps would be redundant
start = i + 1;
deficit += capacity;
capacity = 0;
}
}
return (capacity + deficit >= 0) ? start : -1;
}
// Driver code
var arr = [ new petrolPump(6, 4), new petrolPump(3, 6), new petrolPump(7, 3) ];
var n = arr.length;
var start = printTour(arr, n);
if (start == -1)
document.write("No solution");
else
document.write("Start = " + start);
// This code is contributed by Rajput-Ji
</script>
Producción
Start = 2
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA