Dada una array arr[] de N enteros que representan la posición de N puntos a lo largo de una línea recta y un entero K , la tarea es encontrar el valor mínimo de la distancia máxima entre puntos adyacentes después de agregar K puntos en cualquier punto intermedio, no necesariamente en una posición entera.
Ejemplos:
Entrada: arr[] = {2, 4, 8, 10}, K = 1
Salida: 2
Explicación: Se puede agregar un punto en la posición 6. Entonces, la nueva array de puntos se convierte en {2, 4, 6, 8, 10} y la distancia máxima entre dos puntos adyacentes es 2, que es la mínima posible.Entrada: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, K = 9
Salida: 0,5
Enfoque: el problema dado se puede resolver utilizando la búsqueda binaria . La idea es realizar una búsqueda binaria sobre el valor D en el rango [0, 10 8 ] donde D representa el valor de la distancia máxima entre los puntos adyacentes después de sumar K puntos. Siga los pasos a continuación para resolver el problema dado:
- Inicialice las variables, low = 1 y high = 10 8 , donde low representa el límite inferior y high representa el límite superior de la búsqueda binaria.
- Cree una función isPossible() , que devuelva el valor booleano de si es posible agregar K puntos en la array de modo que la distancia máxima entre puntos adyacentes sea D . Se basa en la observación de que para dos puntos adyacentes (i, j) , el número de puntos necesarios para ser colocados en su medio tal que la distancia máxima entre ellos es D = (j -i)/D .
- Por lo tanto, atraviese el rango usando el algoritmo de búsqueda binaria discutido aquí, y si para el valor medio D en el rango [X, Y] , si isPossible(D) es falso, entonces itere en la mitad superior del rango, es decir, [ D, Y] . De lo contrario, itere en la mitad inferior, es decir, [X, D] .
- Iterar un ciclo hasta (alto – bajo) > 10 -6 .
- El valor almacenado en low es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to check if it is possible
// to add K points such that the maximum
// distance between adjacent points is D
bool isPossible(double D, int arr[],
int N, int K)
{
// Stores the count of point used
int used = 0;
// Iterate over all given points
for (int i = 0; i < N - 1; ++i) {
// Add number of points required
// to be placed between ith
// and (i+1)th point
used += (int)((arr[i + 1]
- arr[i])
/ D);
}
// Return answer
return used <= K;
}
// Function to find the minimum value of
// maximum distance between adjacent points
// after adding K points any where between
double minMaxDist(int stations[], int N, int K)
{
// Stores the lower bound and upper
// bound of the given range
double low = 0, high = 1e8;
// Perform binary search
while (high - low > 1e-6) {
// Find the middle value
double mid = (low + high) / 2.0;
if (isPossible(mid, stations, N, K)) {
// Update the current range
// to lower half
high = mid;
}
// Update the current range
// to upper half
else {
low = mid;
}
}
return low;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int K = 9;
int N = sizeof(arr) / sizeof(arr[0]);
cout << minMaxDist(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.math.BigDecimal;
class GFG {
// Function to check if it is possible
// to add K points such that the maximum
// distance between adjacent points is D
public static boolean isPossible(double D, int arr[],
int N, int K)
{
// Stores the count of point used
int used = 0;
// Iterate over all given points
for (int i = 0; i < N - 1; ++i) {
// Add number of points required
// to be placed between ith
// and (i+1)th point
used += (int) ((arr[i + 1] - arr[i]) / D);
}
// Return answer
return used <= K;
}
// Function to find the minimum value of
// maximum distance between adjacent points
// after adding K points any where between
public static double minMaxDist(int stations[], int N, int K)
{
// Stores the lower bound and upper
// bound of the given range
double low = 0, high = 1e8;
// Perform binary search
while (high - low > 1e-6) {
// Find the middle value
double mid = (low + high) / 2.0;
if (isPossible(mid, stations, N, K)) {
// Update the current range
// to lower half
high = mid;
}
// Update the current range
// to upper half
else {
low = mid;
}
}
// System.out.printf("Value: %.2f", low);
return low;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int K = 9;
int N = arr.length;
System.out.printf("%.1f", minMaxDist(arr, N, K));
}
}
// This code is contributed by _saurabh_jaiswal.
Python3
# Python3 program for the above approach # Function to check if it is possible # to add K points such that the maximum # distance between adjacent points is D def isPossible(D, arr, N, K) : # Stores the count of point used used = 0; # Iterate over all given points for i in range(N - 1) : # Add number of points required # to be placed between ith # and (i+1)th point used += int((arr[i + 1] - arr[i]) / D); # Return answer return used <= K; # Function to find the minimum value of # maximum distance between adjacent points # after adding K points any where between def minMaxDist(stations, N, K) : # Stores the lower bound and upper # bound of the given range low = 0; high = 1e8; # Perform binary search while (high - low > 1e-6) : # Find the middle value mid = (low + high) / 2.0; if (isPossible(mid, stations, N, K)) : # Update the current range # to lower half high = mid; # Update the current range # to upper half else : low = mid; return round(low, 2); # Driver Code if __name__ == "__main__" : arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]; K = 9; N = len(arr); print(minMaxDist(arr, N, K)); # This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
public class GFG {
// Function to check if it is possible
// to add K points such that the maximum
// distance between adjacent points is D
public static bool isPossible(double D, int []arr,
int N, int K)
{
// Stores the count of point used
int used = 0;
// Iterate over all given points
for (int i = 0; i < N - 1; ++i) {
// Add number of points required
// to be placed between ith
// and (i+1)th point
used += (int) ((arr[i + 1] - arr[i]) / D);
}
// Return answer
return used <= K;
}
// Function to find the minimum value of
// maximum distance between adjacent points
// after adding K points any where between
public static double minMaxDist(int []stations, int N, int K)
{
// Stores the lower bound and upper
// bound of the given range
double low = 0, high = 1e8;
// Perform binary search
while (high - low > 1e-6) {
// Find the middle value
double mid = (low + high) / 2.0;
if (isPossible(mid, stations, N, K)) {
// Update the current range
// to lower half
high = mid;
}
// Update the current range
// to upper half
else {
low = mid;
}
}
// Console.Write("Value: %.2f", low);
return low;
}
// Driver Code
public static void Main(String []args)
{
int []arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int K = 9;
int N = arr.Length;
Console.Write("{0:F1}", minMaxDist(arr, N, K));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to check if it is possible
// to add K points such that the maximum
// distance between adjacent points is D
function isPossible(D, arr,
N, K)
{
// Stores the count of point used
let used = 0;
// Iterate over all given points
for (let i = 0; i < N - 1; ++i) {
// Add number of points required
// to be placed between ith
// and (i+1)th point
used += Math.floor((arr[i + 1]
- arr[i])
/ D);
}
// Return answer
return used <= K;
}
// Function to find the minimum value of
// maximum distance between adjacent points
// after adding K points any where between
function minMaxDist(stations, N, K)
{
// Stores the lower bound and upper
// bound of the given range
let low = 0, high = 1e8;
// Perform binary search
while (high - low > 1e-6) {
// Find the middle value
let mid = (low + high) / 2;
if (isPossible(mid, stations, N, K)) {
// Update the current range
// to lower half
high = mid;
}
// Update the current range
// to upper half
else {
low = mid;
}
}
return low.toFixed(1);
}
// Driver Code
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let K = 9;
let N = arr.length;
document.write(minMaxDist(arr, N, K));
// This code is contributed by Potta Lokesh
</script>
Producción:
0.5
Complejidad de tiempo: O(N*log M), donde el valor de M es 10 14 .
Espacio Auxiliar: O(1)
Enfoque alternativo: el problema se reduce a minimizar la distancia máxima K veces. Cada vez, para obtener la distancia máxima, podemos usar el montón máximo.
Paso -1: iterar a través de los elementos de la array y almacenar las distancias de los elementos de la array adyacentes en un montón máximo.
Paso 2: para K veces, sondee el elemento máximo del montón y agregue al montón max/2, max/2, es decir, estamos reduciendo cada vez la distancia máxima a dos mitades iguales.
Paso 3: devuelva el elemento máximo después de iterar K veces.
A continuación se muestra la implementación del enfoque anterior:
C++
#include<bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int K = 9;
int N = sizeof(arr)/sizeof(arr[0]);
// Max heap initialisation
priority_queue<float>pq;
// Add adjacent distances to max heap
for (int i = 1; i < N; i++) {
pq.push((float)arr[i] - (float)arr[i - 1]);
}
// For K times, half the maximum distance
for (int i = 0; i < K; i++) {
float temp = pq.top();
pq.pop();
pq.push(temp / 2);
pq.push(temp / 2);
}
cout<<pq.top()<<endl;
return 0;
}
// This code is contributed by shinjanpatra.
Java
import java.util.Collections;
import java.util.PriorityQueue;
class GFG {
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int K = 9;
int N = arr.length;
// Max heap initialisation
PriorityQueue<Float> pq = new PriorityQueue<>(
N + K, Collections.reverseOrder());
// Add adjacent distances to max heap
for (int i = 1; i < N; i++) {
pq.add((float)arr[i] - (float)arr[i - 1]);
}
// For K times, half the maximum distance
for (int i = 0; i < K; i++) {
float temp = pq.poll();
pq.add(temp / 2);
pq.add(temp / 2);
}
System.out.println(pq.peek());
}
}
// This code is contributed by _govardhani
Python3
# Python3 program for the above approach # importing "bisect" for bisection operations import bisect arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] K = 9 N = len(arr) # Max heap initialisation pq = [] # Add adjacent distances to max heap for i in range(1, N): bisect.insort(pq,float(arr[i])-float(arr[i-1])) # For K times, half the maximum distance for i in range(K): temp=pq[0] pq.pop(0) pq.append(temp/2) pq.append(temp/2) print(pq[0]) # This code is contributed by Pushpesh Raj
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N+K)
Publicación traducida automáticamente
Artículo escrito por kartikey134 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA