Dado N número de coches y un número entero D i.edistancia del destino. Todos los coches parten del mismo punto de partida moviéndose hacia el mismo punto de destino. Las velocidades de cada uno de los autos están dadas por una array speed[] , también sus respectivas posiciones en orden creciente están dadas en una array position[]. Un coche que va a menor velocidad que el anterior se considera un obstáculo para otro. La tarea es hacer que K número de autos lleguen al destino con un número mínimo de intercambios en un tiempo T dado. Un automóvil solo se puede intercambiar con el automóvil que está justo detrás de él, esto se puede hacer con un solo automóvil.
Más de un canje al mismo tiempo, pero cada canje se contará como un canje por separado. Si el número K de automóviles no puede llegar al destino en un tiempo determinado, devuelva -1
Ejemplos :
Entrada : N = 5, K= 3, D = 10, T = 5, posición[] = {0, 2, 5, 6, 7}, velocidad[] = {1, 1, 1, 1, 4}
Salida : 0
Explicación : No se requieren cambios en este caso ya que las velocidades de todos los autos están en orden creciente y los últimos 3 autos pueden llegar fácilmente al destino en el tiempo T
Entrada : N = 5, K = 3, D = 10, T = 5, posición[] = {0, 2, 3, 5, 7}, velocidad[] = {2, 1, 1, 1, 4}
Salida : 2
Explicación : El automóvil que ha recorrido 0 distancia, es decir, en (índice 0) se intercambia con el automóvil en índice 1 y 2 porque ninguno de ellos pudo llegar a destino a tiempo. Después de intercambiar, al menos 3 autos pueden llegar al destino a tiempo.
Entrada : N = 5, K = 3, D = 10, T = 5, posición[] = {0, 2, 3, 4, 7}, velocidad[] = {2, 1, 1, 1, 4}
Salida : -1
Explicación : K número de autos no pudo llegar a destino a tiempo al hacer cualquier número de intercambios.
Enfoque : la tarea se puede resolver utilizando un enfoque codicioso . Dado que las posiciones de cada automóvil se dan en orden creciente , la mejor manera es comenzar a recorrer el último automóvil, manteniendo un contador accesible para los automóviles que pueden llegar al destino a tiempo, y un contador de obstáculos para los automóviles que no pueden llegar . el destino en el tiempo. Si un automóvil puede llegar a tiempo, agregue la cantidad de obstáculos al número de intercambios.
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;
// Function to get minimum
// number of swaps and returns
// number of cars that
// car reach there in time.
int reachables(int x[], int v[], int n,
int& swaps, int d,
int t, int k)
{
// Counter for number of cars that
// can reach in time
int reachable = 0;
// Counter for cars that cannot reach
// destination in time.
int obstacle = 0;
int i = n - 1;
while (i >= 0) {
int temp = d - x[i];
if (v[i] * t >= temp) {
// If a car can reach in
// time then increase the
// reachable counter
reachable++;
// Adding the number of cars
// that need to be swapped
swaps += obstacle;
}
else {
// If a car cannot reach
// in time then increase
// the obstacle counter
obstacle++;
}
if (reachable >= k) {
break;
}
i--;
}
// Return the swaps
if (reachable >= k)
return swaps;
else
return -1;
}
// Driver Code
int main()
{
int n = 5, k = 3, d = 10, t = 5;
int x[] = { 0, 2, 3, 5, 7 };
int v[] = { 2, 1, 1, 1, 4 };
int swaps = 0;
cout << reachables(x, v, n, swaps, d, t, k);
return 0;
}
Java
// Java program for the above approach
class GFG
{
// Function to get minimum
// number of swaps and returns
// number of cars that
// car reach there in time.
static int reachables(int x[], int v[], int n,
int swaps, int d,
int t, int k)
{
// Counter for number of cars that
// can reach in time
int reachable = 0;
// Counter for cars that cannot reach
// destination in time.
int obstacle = 0;
int i = n - 1;
while (i >= 0) {
int temp = d - x[i];
if (v[i] * t >= temp) {
// If a car can reach in
// time then increase the
// reachable counter
reachable++;
// Adding the number of cars
// that need to be swapped
swaps += obstacle;
}
else {
// If a car cannot reach
// in time then increase
// the obstacle counter
obstacle++;
}
if (reachable >= k) {
break;
}
i--;
}
// Return the swaps
if (reachable >= k)
return swaps;
else
return -1;
}
// Driver Code
public static void main(String [] args)
{
int n = 5, k = 3, d = 10, t = 5;
int x[] = { 0, 2, 3, 5, 7 };
int v[] = { 2, 1, 1, 1, 4 };
int swaps = 0;
System.out.println(reachables(x, v, n, swaps, d, t, k));
}
}
// This code is contributed by AR_Gaurav
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to get minimum
// number of swaps and returns
// number of cars that
// car reach there in time.
static int reachables(int []x, int []v, int n,
int swaps, int d,
int t, int k)
{
// Counter for number of cars that
// can reach in time
int reachable = 0;
// Counter for cars that cannot reach
// destination in time.
int obstacle = 0;
int i = n - 1;
while (i >= 0) {
int temp = d - x[i];
if (v[i] * t >= temp) {
// If a car can reach in
// time then increase the
// reachable counter
reachable++;
// Adding the number of cars
// that need to be swapped
swaps += obstacle;
}
else {
// If a car cannot reach
// in time then increase
// the obstacle counter
obstacle++;
}
if (reachable >= k) {
break;
}
i--;
}
// Return the swaps
if (reachable >= k)
return swaps;
else
return -1;
}
// Driver Code
public static void Main(string [] args)
{
int n = 5, k = 3, d = 10, t = 5;
int []x = { 0, 2, 3, 5, 7 };
int []v = { 2, 1, 1, 1, 4 };
int swaps = 0;
Console.WriteLine(reachables(x, v, n, swaps, d, t, k));
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach # Function to get minimum # number of swaps and returns # number of cars that # car reach there in time. def reachables(x, v, n,swaps, d, t, k) : # Counter for number of cars that # can reach in time reachable = 0; # Counter for cars that cannot reach # destination in time. obstacle = 0; i = n - 1; while (i >= 0) : temp = d - x[i]; if (v[i] * t >= temp) : # If a car can reach in # time then increase the # reachable counter reachable += 1; # Adding the number of cars # that need to be swapped swaps += obstacle; else : # If a car cannot reach # in time then increase # the obstacle counter obstacle += 1; if (reachable >= k) : break; i -= 1; # Return the swaps if (reachable >= k) : return swaps; else : return -1; # Driver Code if __name__ == "__main__" : n = 5; k = 3; d = 10; t = 5; x = [ 0, 2, 3, 5, 7 ]; v = [ 2, 1, 1, 1, 4 ]; swaps = 0; print(reachables(x, v, n, swaps, d, t, k)); # This code is contributed by AnkThon
Javascript
<script>
// Javascript program for the above approach
// Function to get minimum
// number of swaps and returns
// number of cars that
// car reach there in time.
function reachables(x, v, n, swaps, d, t, k) {
// Counter for number of cars that
// can reach in time
let reachable = 0;
// Counter for cars that cannot reach
// destination in time.
let obstacle = 0;
let i = n - 1;
while (i >= 0) {
let temp = d - x[i];
if (v[i] * t >= temp) {
// If a car can reach in
// time then increase the
// reachable counter
reachable++;
// Adding the number of cars
// that need to be swapped
swaps += obstacle;
} else {
// If a car cannot reach
// in time then increase
// the obstacle counter
obstacle++;
}
if (reachable >= k) {
break;
}
i--;
}
// Return the swaps
if (reachable >= k) return swaps;
else return -1;
}
// Driver Code
let n = 5,
k = 3,
d = 10,
t = 5;
let x = [0, 2, 3, 5, 7];
let v = [2, 1, 1, 1, 4];
let swaps = 0;
document.write(reachables(x, v, n, swaps, d, t, k));
// This code is contributed by saurabh_jaiswal.
</script>
2
Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)