Dada una array de enteros positivos y un valor K , la tarea es vaciar la array en menos o igual a K arrays pequeñas de modo que cada array pequeña solo pueda contener como máximo P elementos de una sola ranura/índice de la array dada. Encuentre el valor mínimo de P.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5}, K = 7
Salida: 3
Explicación:
Ponemos 1 en la primera array pequeña,
2 en la segunda array,
3 en la tercera array,
después de esto, dividimos los otros elementos como 1 + 3 y 2 + 3
Estos 4 elementos se pueden poner en las 4 cajas restantes.
Entonces, el valor requerido de P es 3.
Entrada: arr[] = {23, 1, 43, 66, 220}, K = 102
Salida: 4
Enfoque: Para resolver este problema necesitamos la búsqueda binaria de la respuesta.
- Primero, establecemos el límite inferior en 1 y el límite superior en el valor máximo de la array dada.
- Ahora, podemos realizar una búsqueda binaria en este rango. Para un valor particular de capacidad, calculamos la cantidad de arrays pequeñas que necesitamos para contener todos los valores de los elementos.
- Si este número requerido de arrays pequeñas es mayor que K, la respuesta es definitivamente mayor, por lo tanto, recortamos el lado izquierdo de la búsqueda. Si es menor o igual a K, mantenemos este valor como posible respuesta y recortamos el lado derecho de la búsqueda.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find the Minimum
// capacity of small arrays needed
// to contain all element of
// the given array
#include <bits/stdc++.h>
using namespace std;
// Function returns the value
// of Minimum capacity needed
int MinimumCapacity(vector<int> arr,
int K)
{
// Initializing maximum
// value
int maxVal = arr[0];
// Finding maximum value
// in arr
for (auto x : arr)
maxVal = max(maxVal, x);
int l = 1, r = maxVal, m;
int ans, req;
// Binary Search the answer
while (l <= r)
{
// m is the mid-point
// of the range
m = l + (r - l) / 2;
req = 0;
// Finding the total number of
// arrays needed to completely
// contain the items array
// with P = req
for (auto x : arr)
req += x / m + (x % m > 0);
// If the required number of
// arrays is more than K, it
// means we need to increase
// the value of P
if (req > K)
l = m + 1;
else
// If the required number of
// arrays is less than or equal
// to K, it means this is a
// possible answer and we go to
// check if any smaller possible
// value exists for P
ans = m, r = m - 1;
}
return ans;
}
// Driver Code
int main()
{
// Given array
vector<int> arr = { 1, 2, 3, 4, 5 };
// Number of available small arrays
int K = 7;
cout << MinimumCapacity(arr, K);
return 0;
}
Java
// Java program to find the Minimum
// capacity of small arrays needed
// to contain all element of
// the given array
class GFG{
// Function returns the value
// of Minimum capacity needed
static int MinimumCapacity(int []arr,
int K)
{
// Initializing maximum
// value
int maxVal = arr[0];
// Finding maximum value
// in arr
for (int x : arr)
maxVal = Math.max(maxVal, x);
int l = 1, r = maxVal, m;
int ans = 0, req;
// Binary Search the answer
while (l <= r)
{
// m is the mid-point
// of the range
m = l + (r - l) / 2;
req = 0;
// Finding the total number of
// arrays needed to completely
// contain the items array
// with P = req
for (int x : arr)
req += x / m + (x % m > 0 ? 1 : 0);
// If the required number of
// arrays is more than K, it
// means we need to increase
// the value of P
if (req > K)
l = m + 1;
else
{
// If the required number of
// arrays is less than or equal
// to K, it means this is a
// possible answer and we go to
// check if any smaller possible
// value exists for P
ans = m;
r = m - 1;
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given array
int []arr = { 1, 2, 3, 4, 5 };
// Number of available small arrays
int K = 7;
System.out.print(MinimumCapacity(arr, K));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find the Minimum # capacity of small arrays needed # to contain all element of # the given array # Function returns the value # of Minimum capacity needed def MinimumCapacity(arr, K): # Initializing maximum # value maxVal = arr[0] # Finding maximum value # in arr for x in arr: maxVal = max(maxVal, x) l = 1 r = maxVal m = 0 ans = 0 req = 0 # Binary Search the answer while l <= r: # m is the mid-point # of the range m = l + (r - l) // 2 req = 0 # Finding the total number of # arrays needed to completely # contain the items array # with P = req for x in arr: req += x // m + (x % m > 0) # If the required number of # arrays is more than K, it # means we need to increase # the value of P if req > K: l = m + 1 else: # If the required number of # arrays is less than or equal # to K, it means this is a # possible answer and we go to # check if any smaller possible # value exists for P ans = m r = m - 1 return ans #Driver Code # Given array arr = [ 1, 2, 3, 4, 5 ] # Number of available small arrays K = 7 print(MinimumCapacity(arr, K)) # This code is contributed by divyamohan123
C#
// C# program to find the minimum
// capacity of small arrays needed
// to contain all element of
// the given array
using System;
class GFG{
// Function returns the value
// of minimum capacity needed
static int MinimumCapacity(int []arr,
int K)
{
// Initializing maximum
// value
int maxVal = arr[0];
// Finding maximum value
// in arr
foreach (int x in arr)
maxVal = Math.Max(maxVal, x);
int l = 1, r = maxVal, m;
int ans = 0, req;
// Binary Search the answer
while (l <= r)
{
// m is the mid-point
// of the range
m = l + (r - l) / 2;
req = 0;
// Finding the total number of
// arrays needed to completely
// contain the items array
// with P = req
foreach (int x in arr)
req += x / m + (x % m > 0 ? 1 : 0);
// If the required number of
// arrays is more than K, it
// means we need to increase
// the value of P
if (req > K)
l = m + 1;
else
{
// If the required number of
// arrays is less than or equal
// to K, it means this is a
// possible answer and we go to
// check if any smaller possible
// value exists for P
ans = m;
r = m - 1;
}
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int []arr = { 1, 2, 3, 4, 5 };
// Number of available small arrays
int K = 7;
Console.Write(MinimumCapacity(arr, K));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to find the minimum
// capacity of small arrays needed
// to contain all element of
// the given array
// Function returns the value
// of minimum capacity needed
function MinimumCapacity(arr, K)
{
// Initializing maximum
// value
let maxVal = arr[0];
// Finding maximum value
// in arr
for(let x = 0; x < arr.length; x++)
maxVal = Math.max(maxVal, arr[x]);
let l = 1, r = maxVal, m;
let ans = 0, req;
// Binary Search the answer
while (l <= r)
{
// m is the mid-point
// of the range
m = l + parseInt((r - l) / 2, 10);
req = 0;
// Finding the total number of
// arrays needed to completely
// contain the items array
// with P = req
for(let x = 0; x < arr.length; x++)
req +=
parseInt(arr[x] / m, 10) + (arr[x] % m > 0 ? 1 : 0);
// If the required number of
// arrays is more than K, it
// means we need to increase
// the value of P
if (req > K)
l = m + 1;
else
{
// If the required number of
// arrays is less than or equal
// to K, it means this is a
// possible answer and we go to
// check if any smaller possible
// value exists for P
ans = m;
r = m - 1;
}
}
return ans;
}
// Given array
let arr = [ 1, 2, 3, 4, 5 ];
// Number of available small arrays
let K = 7;
document.write(MinimumCapacity(arr, K));
</script>
Producción:
3