Dada la circunferencia del círculo y una array pos[] que marca la distancia de N puntos en el círculo en relación con un punto fijo en el sentido de las agujas del reloj. Tenemos que encontrar una distancia mínima a través de la cual podamos visitar todos los puntos. Podemos empezar con cualquier punto.
Ejemplos:
Entrada: circunferencia = 20, pos = [3, 6, 9]
Salida: costo mínimo de ruta = 6
Explicación:
si comenzamos desde 3, vamos a 6 y luego a 9. Por lo tanto, el costo total de ruta es 3 unidades para primer movimiento y 3 unidades para el segundo movimiento que suma 6.
Entrada: circunferencia = 20 pos = [3, 6, 19]
Salida: costo mínimo de ruta = 7
Explicación:
si comenzamos desde 19 y vamos a 3 costará 4 unidades porque vamos de 19 -> 20 -> 1 -> 2 -> 3 que da 4 unidades, y luego 3 a 6 que da 3 unidades. En total el costo mínimo será 4 + 3 = 7.
Enfoque:
para resolver el problema mencionado anteriormente, debemos seguir los pasos que se detallan a continuación:
- Ordena la array que marca la distancia de N puntos en el círculo.
- Haga que el tamaño de la array se duplique agregando el elemento N con el valor arr[i + n] = circumference + arr[i] .
- Encuentre el valor mínimo (arr[i + (n-1)] – arr[i]) para todas las iteraciones válidas del valor i.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// Minimum Cost Path to visit all nodes
// situated at the Circumference of
// Circular Road
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum cost
int minCost(int arr[], int n, int circumference)
{
// Sort the given array
sort(arr, arr + n);
// Initialise a new array of double size
int arr2[2 * n];
// Fill the array elements
for (int i = 0; i < n; i++) {
arr2[i] = arr[i];
arr2[i + n] = arr[i] + circumference;
}
// Find the minimum path cost
int res = INT_MAX;
for (int i = 0; i < n; i++)
res = min(res, arr2[i + (n - 1)] - arr2[i]);
// Return the final result
return res;
}
// Driver code
int main()
{
int arr[] = { 19, 3, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
int circumference = 20;
cout << minCost(arr, n, circumference);
return 0;
}
Java
// Java implementation to find the
// Minimum Cost Path to visit all nodes
// situated at the Circumference of
// Circular Road
import java.util.*;
import java. util. Arrays;
class GFG {
// Function to find the minimum cost
static int minCost(int arr[], int n,
int circumference)
{
// Sort the given array
Arrays.sort(arr);
// Initialise a new array of double size
int[] arr2 = new int[2 * n];
// Fill the array elements
for(int i = 0; i < n; i++)
{
arr2[i] = arr[i];
arr2[i + n] = arr[i] + circumference;
}
// Find the minimum path cost
int res = Integer.MAX_VALUE;
for(int i = 0; i < n; i++)
res = Math.min(res,
arr2[i + (n - 1)] -
arr2[i]);
// Return the final result
return res;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 19, 3, 6 };
int n = arr.length;
int circumference = 20;
System.out.println(minCost(arr, n,
circumference));
}
}
// This code is contributed by ANKITKUMAR34
Python3
# Python3 implementation to find the # minimum cost path to visit all nodes # situated at the circumference of # circular Road # Function to find the minimum cost def minCost(arr, n, circumference): # Sort the given array arr.sort() #Initialise a new array of double size arr2 = [0] * (2 * n) # Fill the array elements for i in range(n): arr2[i] = arr[i] arr2[i + n] = arr[i] + circumference # Find the minimum path cost res = 9999999999999999999; for i in range(n): res = min(res, arr2[i + (n - 1)] - arr2[i]); # Return the final result return res; # Driver code arr = [ 19, 3, 6 ]; n = len(arr) circumference = 20; print(minCost(arr, n, circumference)) # This code is contributed by ANKITKUMAR34
C#
// C# implementation to find the
// Minimum Cost Path to visit all nodes
// situated at the Circumference of
// Circular Road
using System;
class GFG{
// Function to find the minimum cost
static int minCost(int []arr, int n,
int circumference)
{
// Sort the given array
Array.Sort(arr);
// Initialise a new array of double size
int[] arr2 = new int[2 * n];
// Fill the array elements
for(int i = 0; i < n; i++)
{
arr2[i] = arr[i];
arr2[i + n] = arr[i] + circumference;
}
// Find the minimum path cost
int res = int.MaxValue;
for(int i = 0; i < n; i++)
res = Math.Min(res, arr2[i + (n - 1)] -
arr2[i]);
// Return the readonly result
return res;
}
// Driver code
public static void Main(String []args)
{
int []arr = { 19, 3, 6 };
int n = arr.Length;
int circumference = 20;
Console.WriteLine(minCost(arr, n, circumference));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript implementation to find the
// Minimum Cost Path to visit all nodes
// situated at the Circumference of
// Circular Road
// Function to find the minimum cost
function minCost(arr, n,circumference)
{
// Sort the given array
arr.sort((a,b)=>a-b)
// Initialise a new array of double size
var arr2 = Array(2* n).fill(0);
// Fill the array elements
for (var i = 0; i < n; i++) {
arr2[i] = arr[i];
arr2[i + n] = arr[i] + circumference;
}
// Find the minimum path cost
var res = 1000000000;
for (var i = 0; i < n; i++)
res = Math.min(res, arr2[i + (n - 1)] - arr2[i]);
// Return the final result
return res;
}
// Driver code
var arr = [19, 3, 6 ];
var n = arr.length;
var circumference = 20;
document.write( minCost(arr, n, circumference));
</script>
7
Complejidad de tiempo: O(n * log n)
Espacio Auxiliar: O(n)