Dada la cantidad de ciudades n numeradas del 0 al n-1 y las ciudades en las que se encuentran las estaciones, la tarea es encontrar la distancia máxima entre cualquier ciudad y su estación más cercana. Tenga en cuenta que las ciudades con estaciones se pueden dar en cualquier orden.
Ejemplos:
Input: numOfCities = 6, stations = [1, 4] Output: 1 Input: numOfCities = 6, stations = [3] Output: 3 Input: numOfCities = 6, stations = [3, 1] Output: 2
- La siguiente figura representa el primer ejemplo que contiene 6 ciudades y las ciudades con estaciones resaltadas en color verde. En este caso, las ciudades más alejadas de sus estaciones más cercanas son 0, 2, 3 y 5, cada una a una distancia de 1. Por lo tanto, la distancia máxima es 1.
- En el segundo ejemplo, la ciudad más alejada de su estación más cercana es 0, que está a una distancia de 3. Por lo tanto, la distancia máxima es 3.
- En el tercer ejemplo, la ciudad más alejada de su estación más cercana es 5, que está a una distancia de 2. Por lo tanto, la distancia máxima es 2.
Enfoque: Hay tres casos posibles en este problema:
- Cuando la ciudad más lejana se encuentra entre dos estaciones.
- Cuando la ciudad más lejana está del lado izquierdo de la primera estación.
- Cuando la ciudad más lejana está a la derecha de la última estación.
A continuación se muestra el algoritmo para resolver el problema anterior:
- Inicialice una array booleana de tamaño n (número de ciudades) con False . Luego marque los valores de las ciudades con estaciones como True
- Inicialice una variable dist con 0. Inicialice otra variable maxDist con un valor que sea igual a la primera ciudad con la estación (usado para el caso 2).
- Comience a recorrer todas las ciudades una por una.
- Si la ciudad actual tiene una estación, entonces asigne el máximo de ( dist +1)//2 y maxDist a maxDist (usado para el caso 1). Además, asigne 0 a dist .
- De lo contrario, incremente dist .
- Al final, devuelva el máximo de dist y maxDist (usado para el caso 3).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to calculate the maximum
// distance between any city
// and its nearest station
#include<bits/stdc++.h>
using namespace std;
// Function to calculate the maximum
// distance between any city and its nearest station
int findMaxDistance(int numOfCities,int station[],int n)
{
// Initialize boolean list
bool hasStation[numOfCities + 1] = {false};
// Assign True to cities containing station
for (int city = 0; city < n; city++)
{
hasStation[station[city]] = true;
}
int dist = 0;
int maxDist = INT_MAX;
for(int i = 0; i < n; i++)
{
maxDist = min(station[i],maxDist);
}
for (int city = 0; city < numOfCities; city++)
{
if (hasStation[city] == true)
{
maxDist = max((dist + 1) / 2, maxDist);
dist = 0;
}
else
dist += 1;
}
return max(maxDist, dist);
}
//Driver code
int main()
{
int numOfCities = 6;
int station[] = {3, 1};
int n = sizeof(station)/sizeof(station[0]);
cout << "Max Distance:" << findMaxDistance(numOfCities,
station, n);
}
//This code is contributed by Mohit Kumar 29
Java
// Java program to calculate the maximum
// distance between any city
// and its nearest station
import java.util.*;
class GFG
{
// Function to calculate the maximum
// distance between any city and its nearest station
static int findMaxDistance(int numOfCities,
int station[],int n)
{
// Initialize boolean list
boolean hasStation[] = new boolean[numOfCities + 1];
// Assign True to cities containing station
for (int city = 0; city < n; city++)
{
hasStation[station[city]] = true;
}
int dist = 0;
int maxDist = Integer.MAX_VALUE;
for(int i = 0; i < n; i++)
{
maxDist = Math.min(station[i],maxDist);
}
for (int city = 0; city < numOfCities; city++)
{
if (hasStation[city] == true)
{
maxDist = Math.max((dist + 1) / 2, maxDist);
dist = 0;
}
else
dist += 1;
}
return Math.max(maxDist, dist);
}
//Driver code
public static void main(String args[])
{
int numOfCities = 6;
int station[] = {3, 1};
int n = station.length;
System.out.println("Max Distance:"+
findMaxDistance(numOfCities,station, n));
}
}
// This code is contributed by
// Surendra_Gnagwar
Python
# Python3 code to calculate the maximum
# distance between any city and its nearest station
# Function to calculate the maximum
# distance between any city and its nearest station
def findMaxDistance(numOfCities, station):
# Initialize boolean list
hasStation = [False] * numOfCities
# Assign True to cities containing station
for city in station:
hasStation[city] = True
dist, maxDist = 0, min(station)
for city in range(numOfCities):
if hasStation[city] == True:
maxDist = max((dist + 1) // 2, maxDist)
dist = 0
else:
dist += 1
return max(maxDist, dist)
numOfCities = 6
station = [3, 1]
print("Max Distance:", findMaxDistance(numOfCities, station))
C#
// C# program to calculate the maximum
// distance between any city
// and its nearest station
using System;
class GFG
{
// Function to calculate the maximum
// distance between any city and its nearest station
static int findMaxDistance(int numOfCities,
int []station,int n)
{
// Initialize boolean list
bool []hasStation = new bool[numOfCities + 1];
// Assign True to cities containing station
for (int city = 0; city < n; city++)
{
hasStation[station[city]] = true;
}
int dist = 0;
int maxDist = int.MaxValue;
for(int i = 0; i < n; i++)
{
maxDist = Math.Min(station[i],maxDist);
}
for (int city = 0; city < numOfCities; city++)
{
if (hasStation[city] == true)
{
maxDist = Math.Max((dist + 1) / 2, maxDist);
dist = 0;
}
else
dist += 1;
}
return Math.Max(maxDist, dist);
}
// Driver code
public static void Main(String []args)
{
int numOfCities = 6;
int []station = {3, 1};
int n = station.Length;
Console.WriteLine("Max Distance:"+
findMaxDistance(numOfCities,station, n));
}
}
// This code has been contributed by 29AjayKumar
PHP
<?php
// PHP program to calculate the maximum
// distance between any city
// and its nearest station
// Function to calculate the maximum
// distance between any city and
// its nearest station
function findMaxDistance($numOfCities,
$station, $n)
{
// Initialize boolean list
$hasStation = array_fill(0, $numOfCities + 1,
false);
// Assign True to cities containing station
for ($city = 0; $city < $n; $city++)
{
$hasStation[$station[$city]] = true;
}
$dist = 0;
$maxDist = PHP_INT_MAX;
for($i = 0; $i < $n; $i++)
{
$maxDist = min($station[$i], $maxDist);
}
for ($city = 0;
$city < $numOfCities; $city++)
{
if ($hasStation[$city] == true)
{
$maxDist = max((int)(($dist + 1) / 2),
$maxDist);
$dist = 0;
}
else
$dist += 1;
}
return max($maxDist, $dist);
}
// Driver code
$numOfCities = 6;
$station = array(3, 1);
$n = count($station);
echo "Max Distance: ".findMaxDistance($numOfCities,
$station, $n);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to calculate the maximum
// distance between any city
// and its nearest station
// Function to calculate the maximum
// distance between any city and its nearest station
function findMaxDistance(numOfCities,station,n)
{
// Initialize boolean list
var hasStation = Array(numOfCities+1).fill(false);
// Assign True to cities containing station
for (var city = 0; city < n; city++)
{
hasStation[station[city]] = true;
}
var dist = 0;
var maxDist = 1000000000;
for(var i = 0; i < n; i++)
{
maxDist = Math.min(station[i],maxDist);
}
for (var city = 0; city < numOfCities; city++)
{
if (hasStation[city] == true)
{
maxDist = Math.max((dist + 1) / 2, maxDist);
dist = 0;
}
else
dist += 1;
}
return Math.max(maxDist, dist);
}
//Driver code
var numOfCities = 6;
var station = [3, 1];
var n = station.length;
document.write( "Max Distance: " + findMaxDistance(numOfCities,
station, n));
</script>
Producción:
Max Distance: 2
Complejidad temporal: O(n)
Complejidad espacial: O(n)
Publicación traducida automáticamente
Artículo escrito por rituraj_jain y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA