Dada una array cell[] de N elementos, que representan las posiciones de las celdas en una prisión. Además, dado un número entero P que es el número de prisioneros, la tarea es colocar a todos los prisioneros en las celdas de manera ordenada de modo que la distancia mínima entre dos prisioneros sea la mayor posible. Finalmente, imprima la distancia maximizada.
Ejemplos:
Entrada: celda[] = {1, 2, 8, 4, 9}, P = 3
Salida: 3
Los tres presos serán colocados en las celdas
numeradas 1, 4 y 8 con la distancia mínima 3
que es la máxima posible.
Entrada: celda[] = {10, 12, 18}, P = 2
Salida: 8
Las tres ubicaciones posibles son {10, 12}, {10, 18} y {12, 18}.
Enfoque: este problema se puede resolver mediante la búsqueda binaria . Como se debe maximizar la distancia mínima entre dos celdas en las que se mantendrán los reclusos, el espacio de búsqueda será de distancia, comenzando desde 0 (si se retienen dos reclusos en la misma celda) y terminando en la celda [N – 1] – celda[0] (si un recluso se mantiene en la primera celda y el otro en la última celda).
Inicialice L = 0 y R = celda [N – 1] – celda [0] y luego aplique la búsqueda binaria. Para cada medio , verifique si los prisioneros pueden colocarse de manera que la distancia mínima entre dos prisioneros sea al menos medio .
- En caso afirmativo, intente aumentar esta distancia para maximizar la respuesta y verifique nuevamente.
- Si no es así, intente disminuir la distancia.
- Finalmente, imprima la distancia maximizada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns true if the prisoners
// can be placed such that the minimum distance
// between any two prisoners is at least sep
bool canPlace(int a[], int n, int p, int sep)
{
// Considering the first prisoner
// is placed at 1st cell
int prisoners_placed = 1;
// If the first prisoner is placed at
// the first cell then the last_prisoner_placed
// will be the first prisoner placed
// and that will be in cell[0]
int last_prisoner_placed = a[0];
for (int i = 1; i < n; i++) {
int current_cell = a[i];
// Checking if the prisoner can be
// placed at ith cell or not
if (current_cell - last_prisoner_placed >= sep) {
prisoners_placed++;
last_prisoner_placed = current_cell;
// If all the prisoners got placed
// then return true
if (prisoners_placed == p) {
return true;
}
}
}
return false;
}
// Function to return the maximized distance
int maxDistance(int cell[], int n, int p)
{
// Sort the array so that binary
// search can be applied on it
sort(cell, cell + n);
// Minimum possible distance
// for the search space
int start = 0;
// Maximum possible distance
// for the search space
int end = cell[n - 1] - cell[0];
// To store the result
int ans = 0;
// Binary search
while (start <= end) {
int mid = start + ((end - start) / 2);
// If the prisoners can be placed such that
// the minimum distance between any two
// prisoners is at least mid
if (canPlace(cell, n, p, mid)) {
// Update the answer
ans = mid;
start = mid + 1;
}
else {
end = mid - 1;
}
}
return ans;
}
// Driver code
int main()
{
int cell[] = { 1, 2, 8, 4, 9 };
int n = sizeof(cell) / sizeof(int);
int p = 3;
cout << maxDistance(cell, n, p);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function that returns true if the prisoners
// can be placed such that the minimum distance
// between any two prisoners is at least sep
static boolean canPlace(int a[], int n, int p, int sep)
{
// Considering the first prisoner
// is placed at 1st cell
int prisoners_placed = 1;
// If the first prisoner is placed at
// the first cell then the last_prisoner_placed
// will be the first prisoner placed
// and that will be in cell[0]
int last_prisoner_placed = a[0];
for (int i = 1; i < n; i++)
{
int current_cell = a[i];
// Checking if the prisoner can be
// placed at ith cell or not
if (current_cell - last_prisoner_placed >= sep)
{
prisoners_placed++;
last_prisoner_placed = current_cell;
// If all the prisoners got placed
// then return true
if (prisoners_placed == p)
{
return true;
}
}
}
return false;
}
// Function to return the maximized distance
static int maxDistance(int cell[], int n, int p)
{
// Sort the array so that binary
// search can be applied on it
Arrays.sort(cell);
// Minimum possible distance
// for the search space
int start = 0;
// Maximum possible distance
// for the search space
int end = cell[n - 1] - cell[0];
// To store the result
int ans = 0;
// Binary search
while (start <= end)
{
int mid = start + ((end - start) / 2);
// If the prisoners can be placed such that
// the minimum distance between any two
// prisoners is at least mid
if (canPlace(cell, n, p, mid))
{
// Update the answer
ans = mid;
start = mid + 1;
}
else
{
end = mid - 1;
}
}
return ans;
}
// Driver code
public static void main (String[] args)
{
int cell[] = { 1, 2, 8, 4, 9 };
int n = cell.length;
int p = 3;
System.out.println(maxDistance(cell, n, p));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function that returns true if the prisoners # can be placed such that the minimum distance # between any two prisoners is at least sep def canPlace(a, n, p, sep): # Considering the first prisoner # is placed at 1st cell prisoners_placed = 1 # If the first prisoner is placed at # the first cell then the last_prisoner_placed # will be the first prisoner placed # and that will be in cell[0] last_prisoner_placed = a[0] for i in range(1, n): current_cell = a[i] # Checking if the prisoner can be # placed at ith cell or not if (current_cell - last_prisoner_placed >= sep): prisoners_placed += 1 last_prisoner_placed = current_cell # If all the prisoners got placed # then return true if (prisoners_placed == p): return True return False # Function to return the maximized distance def maxDistance(cell, n, p): # Sort the array so that binary # search can be applied on it cell = sorted(cell) # Minimum possible distance # for the search space start = 0 # Maximum possible distance # for the search space end = cell[n - 1] - cell[0] # To store the result ans = 0 # Binary search while (start <= end): mid = start + ((end - start) // 2) # If the prisoners can be placed such that # the minimum distance between any two # prisoners is at least mid if (canPlace(cell, n, p, mid)): # Update the answer ans = mid start = mid + 1 else : end = mid - 1 return ans # Driver code cell= [1, 2, 8, 4, 9] n = len(cell) p = 3 print(maxDistance(cell, n, p)) # This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
using System.Collections;
class GFG
{
// Function that returns true if the prisoners
// can be placed such that the minimum distance
// between any two prisoners is at least sep
static bool canPlace(int []a, int n,
int p, int sep)
{
// Considering the first prisoner
// is placed at 1st cell
int prisoners_placed = 1;
// If the first prisoner is placed at
// the first cell then the last_prisoner_placed
// will be the first prisoner placed
// and that will be in cell[0]
int last_prisoner_placed = a[0];
for (int i = 1; i < n; i++)
{
int current_cell = a[i];
// Checking if the prisoner can be
// placed at ith cell or not
if (current_cell - last_prisoner_placed >= sep)
{
prisoners_placed++;
last_prisoner_placed = current_cell;
// If all the prisoners got placed
// then return true
if (prisoners_placed == p)
{
return true;
}
}
}
return false;
}
// Function to return the maximized distance
static int maxDistance(int []cell, int n, int p)
{
// Sort the array so that binary
// search can be applied on it
Array.Sort(cell);
// Minimum possible distance
// for the search space
int start = 0;
// Maximum possible distance
// for the search space
int end = cell[n - 1] - cell[0];
// To store the result
int ans = 0;
// Binary search
while (start <= end)
{
int mid = start + ((end - start) / 2);
// If the prisoners can be placed such that
// the minimum distance between any two
// prisoners is at least mid
if (canPlace(cell, n, p, mid))
{
// Update the answer
ans = mid;
start = mid + 1;
}
else
{
end = mid - 1;
}
}
return ans;
}
// Driver code
public static void Main()
{
int []cell = { 1, 2, 8, 4, 9 };
int n = cell.Length;
int p = 3;
Console.WriteLine(maxDistance(cell, n, p));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// javascript implementation of the approach
// Function that returns true if the prisoners
// can be placed such that the minimum distance
// between any two prisoners is at least sep
function canPlace(a , n , p , sep)
{
// Considering the first prisoner
// is placed at 1st cell
var prisoners_placed = 1;
// If the first prisoner is placed at
// the first cell then the last_prisoner_placed
// will be the first prisoner placed
// and that will be in cell[0]
var last_prisoner_placed = a[0];
for (i = 1; i < n; i++)
{
var current_cell = a[i];
// Checking if the prisoner can be
// placed at ith cell or not
if (current_cell - last_prisoner_placed >= sep)
{
prisoners_placed++;
last_prisoner_placed = current_cell;
// If all the prisoners got placed
// then return true
if (prisoners_placed == p)
{
return true;
}
}
}
return false;
}
// Function to return the maximized distance
function maxDistance(cell , n , p)
{
// Sort the array so that binary
// search can be applied on it
cell.sort();
// Minimum possible distance
// for the search space
var start = 0;
// Maximum possible distance
// for the search space
var end = cell[n - 1] - cell[0];
// To store the result
var ans = 0;
// Binary search
while (start <= end)
{
var mid = start + parseInt(((end - start) / 2));
// If the prisoners can be placed such that
// the minimum distance between any two
// prisoners is at least mid
if (canPlace(cell, n, p, mid))
{
// Update the answer
ans = mid;
start = mid + 1;
}
else
{
end = mid - 1;
}
}
return ans;
}
// Driver code
var cell = [ 1, 2, 8, 4, 9 ];
var n = cell.length;
var p = 3;
document.write(maxDistance(cell, n, p));
// This code is contributed by Rajput-Ji
</script>
Producción:
3
Publicación traducida automáticamente
Artículo escrito por mishrakishan1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA