Dado un número entero K que denota la capacidad del depósito de combustible de un automóvil que circula al costo de 1 litro/mtr en un camino recto de longitud N metros y dos conjuntos a[] y b[], cada uno de tamaño M, donde a[i] denota la ubicación de la i -ésima estación y b[i] denota el costo de 1 litro de combustible en esa estación. La tarea es encontrar el costo mínimo requerido para llegar al final de la línea, comenzando desde 0 . Si no es posible llegar al final, imprima -1 .
Ejemplos:
Entrada: N = 10, K = 10, M = 2, a[] = {0, 1}, b[] = {5, 2}
Salida: 23
Explicación:
en la ubicación 0, llene el tanque del automóvil con 1 litro de combustible a un costo de 5. Luego, en la 1ra ubicación, llene 9 litros de combustible a un costo de 18.
Por lo tanto, el costo mínimo requerido es de 23.Entrada: N = 10, K = 5, M = 3, a[] = {0, 3, 5}, b[] = {5, 9, 3}
Salida: 40
Enfoque: La idea es usar Priority Queue y HashMap para almacenar las estaciones de combustible para obtener la estación de combustible con un costo mínimo. Siga los pasos a continuación para resolver el problema:
- Inicializar un HashMap , digamos mapa, para almacenar el índice de la estación y su respectiva tasa de combustible.
- Inicialice una cola de prioridad , digamos pq, para almacenar el índice de la estación y el costo del combustible y los litros de combustible que se están llenando.
- Inicialice dos variables, digamos costo, para almacenar el costo mínimo requerido y establezca flag = false para verificar si hay estaciones de servicio o no.
- Iterar sobre el rango [1, N] :
- Compruebe si hay una estación o no. Si se encuentra que es cierto, insértelo en pq .
- Retire todas las estaciones en las que no se pueda repostar combustible.
- Si pq está vacío , entonces no es posible llegar al final de la línea. Por lo tanto, establezca flag = true .
- Almacene la estación de menor costo y actualice el costo y la cantidad de litros bombeados desde esa estación en particular.
- Insértelo de nuevo en pq .
- Si la bandera es verdadera, imprima «-1». Significa que no hay estaciones de servicio. Por lo tanto, no es posible llegar al final de la línea.
- De lo contrario, imprima el costo mínimo para llegar al final de la línea.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// For priority_queue
struct Compare {
bool operator()(array<int, 3> a, array<int, 3> b)
{
return a[1] > b[1];
}
};
// Function to calculate the minimum cost
// required to reach the end of Line
void minCost(int N, int K, int M, int a[], int b[])
{
// Checks if possible to
// reach end or not
bool flag = true;
// Stores the stations and
// respective rate of fuel
unordered_map<int, int> map;
for (int i = 0; i < M; i++) {
map[a[i]] = b[i];
if (i == M - 1 && K < N - a[i]) {
flag = false;
break;
}
else if (i < M - 1 && K < a[i + 1] - a[i]) {
flag = false;
break;
}
}
if (!flag) {
cout << -1;
return;
}
// Stores the station index and cost of fuel and
// litres of petrol which is being fueled
priority_queue<array<int, 3>, vector<array<int, 3> >,
Compare>
pq;
int cost = 0;
flag = false;
// Iterate through the entire line
for (int i = 0; i < N; i++) {
// Check if there is a station at current index
if (map.find(i) != map.end()) {
array<int, 3> arr = { i, map[i], 0 };
pq.push(arr);
}
// Remove all the stations where
// fuel cannot be pumped
while (pq.size() > 0 && pq.top()[2] == K)
pq.pop();
// If there is no station left to fill fuel
// in tank, it is not possible to reach end
if (pq.size() == 0) {
flag = true;
break;
}
// Stores the best station
// visited so far
array<int, 3> best_bunk = pq.top();
pq.pop();
// Pump fuel from the best station
cost += best_bunk[1];
// Update the count of litres
// taken from that station
best_bunk[2]++;
// Update the bunk in queue
pq.push(best_bunk);
}
if (flag) {
cout << -1 << "\n";
return;
}
// Print the cost
cout << cost << "\n";
}
// Driven Program
int main()
{
// Given value of N, K & M
int N = 10, K = 3, M = 4;
// Given arrays
int a[] = { 0, 1, 4, 6 };
int b[] = { 5, 2, 2, 4 };
// Function call to calculate minimum
// cost to reach end of the line
minCost(N, K, M, a, b);
return 0;
}
// This code is contributed by Kingash.
Java
// Java program for the above approach
import java.util.*;
public class Main {
// Function to calculate the minimum cost
// required to reach the end of Line
static void minCost(int N, int K, int M,
int[] a, int[] b)
{
// Checks if possible to
// reach end or not
boolean flag = true;
// Stores the stations and
// respective rate of fuel
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < M; i++) {
map.put(a[i], b[i]);
if (i == M - 1 && K < N - a[i]) {
flag = false;
break;
}
else if (i < M - 1 && K < a[i + 1] - a[i]) {
flag = false;
break;
}
}
if (!flag) {
System.out.println("-1");
return;
}
// Stores the station index and cost of fuel and
// litres of petrol which is being fueled
PriorityQueue<int[]> pq
= new PriorityQueue<>((c, d) -> c[1] - d[1]);
int cost = 0;
flag = false;
// Iterate through the entire line
for (int i = 0; i < N; i++) {
// Check if there is a station at current index
if (map.containsKey(i))
pq.add(new int[] { i, map.get(i), 0 });
// Remove all the stations where
// fuel cannot be pumped
while (pq.size() > 0 && pq.peek()[2] == K)
pq.poll();
// If there is no station left to fill fuel
// in tank, it is not possible to reach end
if (pq.size() == 0) {
flag = true;
break;
}
// Stores the best station
// visited so far
int best_bunk[] = pq.poll();
// Pump fuel from the best station
cost += best_bunk[1];
// Update the count of litres
// taken from that station
best_bunk[2]++;
// Update the bunk in queue
pq.add(best_bunk);
}
if (flag) {
System.out.println("-1");
return;
}
// Print the cost
System.out.println(cost);
}
// Driver Code
public static void main(String args[])
{
// Given value of N, K & M
int N = 10, K = 3, M = 4;
// Given arrays
int a[] = { 0, 1, 4, 6 };
int b[] = { 5, 2, 2, 4 };
// Function call to calculate minimum
// cost to reach end of the line
minCost(N, K, M, a, b);
}
}
Python3
# Python3 program for the above approach
# Function to calculate the minimum cost
# required to reach the end of Line
def minCost(N, K, M, a, b):
# Checks if possible to
# reach end or not
flag = True
# Stores the stations and
# respective rate of fuel
map = {}
for i in range(M):
map[a[i]] = b[i]
if (i == M - 1 and K < N - a[i]):
flag = False
break
elif (i < M - 1 and K < a[i + 1] - a[i]):
flag = False
break
if (flag == 0):
print(-1)
return
# Stores the station index and cost of fuel and
# litres of petrol which is being fueled
pq = []
cost = 0
flag = False
# Iterate through the entire line
for i in range(N):
# Check if there is a station at current index
if (i in map):
arr = [ i, map[i], 0 ]
pq.append(arr)
pq.sort()
# Remove all the stations where
# fuel cannot be pumped
while (len(pq) > 0 and pq[-1][2] == K):
pq.pop()
# If there is no station left to fill fuel
# in tank, it is not possible to reach end
if (len(pq) == 0):
flag = True
break
# Stores the best station
# visited so far
best_bunk = pq[len(pq)-1]
pq.pop()
# Pump fuel from the best station
cost += best_bunk[1]
# Update the count of litres
# taken from that station
best_bunk[2] += 1
# Update the bunk in queue
pq.append(best_bunk)
pq.sort()
if (flag):
print( -1)
return
# Print the cost
print(cost)
# Driven Program
# Given value of N, K & M
N,K,M = 10,3,4
# Given arrays
a = [0, 1, 4, 6]
b = [5, 2, 2, 4]
# Function call to calculate minimum
# cost to reach end of the line
minCost(N, K, M, a, b)
# This code is contributed by shinjanpatra
Javascript
<script>
// Javascript program for the above approach
// Function to calculate the minimum cost
// required to reach the end of Line
function minCost(N, K, M, a, b)
{
// Checks if possible to
// reach end or not
var flag = true;
// Stores the stations and
// respective rate of fuel
var map = new Map();
for (var i = 0; i < M; i++) {
map.set(a[i] , b[i]);
if (i == M - 1 && K < N - a[i]) {
flag = false;
break;
}
else if (i < M - 1 && K < a[i + 1] - a[i]) {
flag = false;
break;
}
}
if (!flag) {
document.write(-1);
return;
}
// Stores the station index and cost of fuel and
// litres of petrol which is being fueled
var pq = [];
var cost = 0;
flag = false;
// Iterate through the entire line
for (var i = 0; i < N; i++) {
// Check if there is a station at current index
if (map.has(i)) {
var arr = [ i, map.get(i), 0 ];
pq.push(arr);
}
pq.sort();
// Remove all the stations where
// fuel cannot be pumped
while (pq.length > 0 && pq[pq.length-1][2] == K)
pq.pop();
// If there is no station left to fill fuel
// in tank, it is not possible to reach end
if (pq.length == 0) {
flag = true;
break;
}
// Stores the best station
// visited so far
var best_bunk = pq[pq.length-1];
pq.pop();
// Pump fuel from the best station
cost += best_bunk[1];
// Update the count of litres
// taken from that station
best_bunk[2]++;
// Update the bunk in queue
pq.push(best_bunk);
pq.sort();
}
if (flag) {
document.write( -1 + "<br>");
return;
}
// Print the cost
document.write(cost + "<br>");
}
// Driven Program
// Given value of N, K & M
var N = 10, K = 3, M = 4;
// Given arrays
var a = [0, 1, 4, 6 ];
var b = [5, 2, 2, 4];
// Function call to calculate minimum
// cost to reach end of the line
minCost(N, K, M, a, b);
// This code is contributed by rutvik_56.
</script>
Producción:
-1
Complejidad temporal: O(N * logN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA