Dada una array de N enteros que denota los bordes de N estructuras cúbicas respectivamente. También se dan los enteros M que denotan el número de pueblos. La tarea es encontrar la cantidad máxima de volumen de un cubo que se le puede dar a cada persona.
Nota : Los cubos se pueden cortar de cualquier forma de cualquiera de los N cubos.
Ejemplos:
Entrada: a[] = {1, 1, 1, 2, 2}, m = 3
Salida: 4
Las tres personas obtienen una porción del volumen 4 cada
Persona 1 obtiene una porción del volumen 4 del último cubo.
La persona 2 obtiene una porción del volumen 4 del último cubo.
La persona 3 obtiene una porción del volumen 4 del penúltimo cubo.
Entrada: a[] = {2, 2, 2, 2, 2}, m = 4
Salida: 8
Enfoque ingenuo : un enfoque ingenuo es calcular primero el volumen de todos los cubos y luego verificar linealmente para cada volumen que se puede distribuir entre todas las M personas o no y encontrar el volumen máximo entre todos esos volúmenes.
Complejidad temporal: O(N 2 )
Enfoque eficiente : un enfoque eficiente es utilizar la búsqueda binaria para encontrar la respuesta. Dado que las longitudes de los bordes se dan en la array, conviértalas al volumen de los cubos respectivos. Encuentra el volumen máximo entre los volúmenes de todos los cubos. Digamos que el volumen máximo es maxVolume . Ahora, realice una búsqueda binaria en el rango [0, maxVolume].
- Calcule el valor medio del rango, digamos mid.
- Ahora, calcula el número total de cubos que se pueden cortar de todos los cubos de volumen medio .
- Si el total de cubos que se pueden cortar excede el número de personas, entonces esa cantidad de volumen de cubos se puede cortar para cada persona, por lo tanto, buscamos un valor mayor en el rango [mid+1, maxVolume] .
- Si los cubos totales no exceden el número de personas, buscamos una respuesta en el rango [bajo, medio-1] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to get the maximum volume that
// every person can get
int getMaximumVloume(int a[], int n, int m)
{
int maxVolume = 0;
// Convert the length to respective volumes
// and find the maximum volumes
for (int i = 0; i < n; i++) {
a[i] = a[i] * a[i] * a[i];
maxVolume = max(a[i], maxVolume);
}
// Apply binary search with initial
// low as 0 and high as the maximum most
int low = 0, high = maxVolume;
// Initial answer is 0 slices
int maxVol = 0;
// Apply binary search
while (low <= high) {
// Get the mid element
int mid = (low + high) >> 1;
// Count the slices of volume mid
int cnt = 0;
for (int i = 0; i < n; i++) {
cnt += a[i] / mid;
}
// If the slices of volume
// exceeds the number of persons
// then every person can get volume mid
if (cnt >= m) {
// Then check for larger in the right half
low = mid + 1;
// Replace tbe answer with
// current maximum i.e., mid
maxVol = max(maxVol, mid);
}
// else traverse in the left half
else
high = mid - 1;
}
return maxVol;
}
// Driver code
int main()
{
int a[] = { 1, 1, 1, 2, 2 };
int n = sizeof(a) / sizeof(a[0]);
int m = 3;
cout << getMaximumVloume(a, n, m);
return 0;
}
Java
// Java program to implement the above approach
class GFG
{
// Function to get the maximum volume that
// every person can get
static int getMaximumVloume(int a[], int n, int m)
{
int maxVolume = 0;
// Convert the length to respective volumes
// and find the maximum volumes
for (int i = 0; i < n; i++)
{
a[i] = a[i] * a[i] * a[i];
maxVolume = Math.max(a[i], maxVolume);
}
// Apply binary search with initial
// low as 0 and high as the maximum most
int low = 0, high = maxVolume;
// Initial answer is 0 slices
int maxVol = 0;
// Apply binary search
while (low <= high)
{
// Get the mid element
int mid = (low + high) >> 1;
// Count the slices of volume mid
int cnt = 0;
for (int i = 0; i < n; i++)
{
cnt += a[i] / mid;
}
// If the slices of volume
// exceeds the number of persons
// then every person can get volume mid
if (cnt >= m)
{
// Then check for larger in the right half
low = mid + 1;
// Replace tbe answer with
// current maximum i.e., mid
maxVol = Math.max(maxVol, mid);
}
// else traverse in the left half
else
{
high = mid - 1;
}
}
return maxVol;
}
// Driver code
public static void main(String[] args)
{
int a[] = {1, 1, 1, 2, 2};
int n = a.length;
int m = 3;
System.out.println(getMaximumVloume(a, n, m));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program to implement # the above approach # Function to get the maximum volume # that every person can get def getMaximumVloume(a, n, m): maxVolume = 0 # Convert the length to respective # volumes and find the maximum volumes for i in range(n): a[i] = a[i] * a[i] * a[i] maxVolume = max(a[i], maxVolume) # Apply binary search with initial # low as 0 and high as the maximum most low = 0 high = maxVolume # Initial answer is 0 slices maxVol = 0 # Apply binary search while (low <= high): # Get the mid element mid = (low + high) >> 1 # Count the slices of volume mid cnt = 0 for i in range(n): cnt += int(a[i] / mid) # If the slices of volume # exceeds the number of persons # then every person can get volume mid if (cnt >= m): # Then check for larger in the right half low = mid + 1 # Replace tbe answer with # current maximum i.e., mid maxVol = max(maxVol, mid) # else traverse in the left half else: high = mid - 1 return maxVol # Driver code if __name__ == '__main__': a = [1, 1, 1, 2, 2] n = len(a) m = 3 print(getMaximumVloume(a, n, m)) # This code is contributed # by Surendra_Gangwar
C#
// C# program to implement the above approach
using System;
class GFG
{
// Function to get the maximum volume that
// every person can get
static int getMaximumVloume(int []a, int n, int m)
{
int maxVolume = 0;
// Convert the length to respective volumes
// and find the maximum volumes
for (int i = 0; i < n; i++)
{
a[i] = a[i] * a[i] * a[i];
maxVolume = Math.Max(a[i], maxVolume);
}
// Apply binary search with initial
// low as 0 and high as the maximum most
int low = 0, high = maxVolume;
// Initial answer is 0 slices
int maxVol = 0;
// Apply binary search
while (low <= high)
{
// Get the mid element
int mid = (low + high) >> 1;
// Count the slices of volume mid
int cnt = 0;
for (int i = 0; i < n; i++)
{
cnt += a[i] / mid;
}
// If the slices of volume
// exceeds the number of persons
// then every person can get volume mid
if (cnt >= m)
{
// Then check for larger in the right half
low = mid + 1;
// Replace tbe answer with
// current maximum i.e., mid
maxVol = Math.Max(maxVol, mid);
}
// else traverse in the left half
else
{
high = mid - 1;
}
}
return maxVol;
}
// Driver code
public static void Main(String[] args)
{
int []a = {1, 1, 1, 2, 2};
int n = a.Length;
int m = 3;
Console.WriteLine(getMaximumVloume(a, n, m));
}
}
/* This code contributed by PrinciRaj1992 */
PHP
<?php
// PHP program to implement the above approach
// Function to get the maximum volume that
// every person can get
function getMaximumVloume($a, $n, $m)
{
$maxVolume = 0;
// Convert the length to respective volumes
// and find the maximum volumes
for ($i = 0; $i < $n; $i++)
{
$a[$i] = $a[$i] * $a[$i] * $a[$i];
$maxVolume = max($a[$i], $maxVolume);
}
// Apply binary search with initial
// low as 0 and high as the maximum most
$low = 0; $high = $maxVolume;
// Initial answer is 0 slices
$maxVol = 0;
// Apply binary search
while ($low <= $high)
{
// Get the mid element
$mid = ($low + $high) >> 1;
// Count the slices of volume mid
$cnt = 0;
for ($i = 0; $i < $n; $i++)
{
$cnt += (int)($a[$i] / $mid);
}
// If the slices of volume
// exceeds the number of persons
// then every person can get volume mid
if ($cnt >= $m)
{
// Then check for larger in the right half
$low = $mid + 1;
// Replace tbe answer with
// current maximum i.e., mid
$maxVol = max($maxVol, $mid);
}
// else traverse in the left half
else
$high = $mid - 1;
}
return $maxVol;
}
// Driver code
$a = array(1, 1, 1, 2, 2);
$n = sizeof($a);
$m = 3;
echo getMaximumVloume($a, $n, $m);
// This code is contributed by Akanksha Rai
?>
Javascript
<script>
// javascript program to implement the above approach
// Function to get the maximum volume that
// every person can get
function getMaximumVloume(a , n , m) {
var maxVolume = 0;
// Convert the length to respective volumes
// and find the maximum volumes
for (i = 0; i < n; i++) {
a[i] = a[i] * a[i] * a[i];
maxVolume = Math.max(a[i], maxVolume);
}
// Apply binary search with initial
// low as 0 and high as the maximum most
var low = 0, high = maxVolume;
// Initial answer is 0 slices
var maxVol = 0;
// Apply binary search
while (low <= high) {
// Get the mid element
var mid = (low + high) >> 1;
// Count the slices of volume mid
var cnt = 0;
for (i = 0; i < n; i++) {
cnt += parseInt(a[i] / mid);
}
// If the slices of volume
// exceeds the number of persons
// then every person can get volume mid
if (cnt >= m) {
// Then check for larger in the right half
low = mid + 1;
// Replace tbe answer with
// current maximum i.e., mid
maxVol = Math.max(maxVol, mid);
}
// else traverse in the left half
else {
high = mid - 1;
}
}
return maxVol;
}
// Driver code
var a = [ 1, 1, 1, 2, 2 ];
var n = a.length;
var m = 3;
document.write(getMaximumVloume(a, n, m));
// This code is contributed by todaysgaurav
</script>
Producción:
4
Complejidad de tiempo: O(N * log(maxVolume)), ya que estamos usando bucles anidados, el bucle externo atraviesa log(maxVolume) veces, ya que en cada recorrido hacemos un desplazamiento a la derecha de 1 bit, lo que equivale a la división de piso de 2, por lo tanto, el el tiempo efectivo será 1+1/2+1/4+…..+1/2^maxVolume que es equivalente a log(maxVolume), el ciclo interno atraviesa N veces.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.