Dada una array arr[] que consta de N enteros que representan el número de monedas en cada montón, y un número entero H , la tarea es encontrar el número mínimo de monedas que se deben recolectar de un solo montón por hora de modo que todos los montones sean vaciado en menos de H horas.
Nota: Las monedas solo se pueden recolectar de una sola pila en una hora.
Ejemplos:
Entrada: arr[] = {3, 6, 7, 11}, H = 8
Salida: 4
Explicación:
Retirando 4 monedas por montón en cada hora, el tiempo necesario para vaciar cada montón es el siguiente:
arr[0] = 3 : Vaciado en 1 hora.
arr[1] = 6: 4 monedas extraídas en la 1ª hora y 2 extraídas en la 2ª hora. Por lo tanto, se vacía en 2 horas.
arr[2] = 7: 4 monedas extraídas en la 1ª hora y 3 extraídas en la 2ª hora. Por lo tanto, se vacía en 2 horas.
arr[3] = 11: 4 monedas extraídas tanto en la 1ª como en la 2ª hora, y 3 extraídas en la 3ª hora. Por lo tanto, se vacía en 3 horas.
Por lo tanto, número de horas requeridas = 1 + 2 + 2 + 3 = 8 ( = H).Entrada: arr[] = {30, 11, 23, 4, 20}, H = 5
Salida: 30
Enfoque: La idea es utilizar Binary Search . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans , para almacenar el número mínimo de monedas que se deben recolectar por hora.
- Inicialice las variables low y high , como 1 y el valor máximo presente en la array , para establecer el rango para realizar la búsqueda binaria .
- Iterar hasta bajo ≤ alto y realizar los siguientes pasos:
- Encuentre el valor de mid como (low + high)/2 .
- Recorra la array arr[] para encontrar el tiempo necesario para vaciar todo el montón de monedas quitando la mitad de las monedas por hora y verifique si el tiempo total excede H o no. Si se encuentra que es falso, actualice el alto a (K – 1) y actualice ans a K. De lo contrario, actualice bajo a (K + 1) .
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number
// of coins to be collected per hour
// to empty N piles in H hours
int minCollectingSpeed(vector<int>& piles,
int H)
{
// Stores the minimum coins
// to be removed per hour
int ans = -1;
int low = 1, high;
// Find the maximum array element
high = *max_element(piles.begin(),
piles.end());
// Perform Binary Search
while (low <= high)
{
// Store the mid value of the
// range in K
int K = low + (high - low) / 2;
int time = 0;
// Find the total time taken to
// empty N piles by removing K
// coins per hour
for (int ai : piles) {
time += (ai + K - 1) / K;
}
// If total time does not exceed H
if (time <= H) {
ans = K;
high = K - 1;
}
// Otherwise
else {
low = K + 1;
}
}
// Print the required result
cout << ans;
}
// Driver Code
int main()
{
vector<int> arr = { 3, 6, 7, 11 };
int H = 8;
// Function Call
minCollectingSpeed(arr, H);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the minimum number
// of coins to be collected per hour
// to empty N piles in H hours
static void minCollectingSpeed(int[] piles,
int H)
{
// Stores the minimum coins
// to be removed per hour
int ans = -1;
int low = 1, high;
// Find the maximum array element
high = Arrays.stream(piles).max().getAsInt();
// Perform Binary Search
while (low <= high)
{
// Store the mid value of the
// range in K
int K = low + (high - low) / 2;
int time = 0;
// Find the total time taken to
// empty N piles by removing K
// coins per hour
for(int ai : piles)
{
time += (ai + K - 1) / K;
}
// If total time does not exceed H
if (time <= H)
{
ans = K;
high = K - 1;
}
// Otherwise
else
{
low = K + 1;
}
}
// Print the required result
System.out.print(ans);
}
// Driver Code
static public void main(String args[])
{
int[] arr = { 3, 6, 7, 11 };
int H = 8;
// Function Call
minCollectingSpeed(arr, H);
}
}
// This code is contributed by sanjoy_62
C#
// C# program for the above approach
using System;
using System.Collections;
class GFG
{
// Function to find the minimum number
// of coins to be collected per hour
// to empty N piles in H hours
static void minCollectingSpeed(int[] piles,
int H)
{
// Stores the minimum coins
// to be removed per hour
int ans = -1;
int low = 1, high;
Array.Sort(piles);
// Find the maximum array element
high = piles[piles.Length - 1 ];
// Perform Binary Search
while (low <= high)
{
// Store the mid value of the
// range in K
int K = low + (high - low) / 2;
int time = 0;
// Find the total time taken to
// empty N piles by removing K
// coins per hour
foreach(int ai in piles)
{
time += (ai + K - 1) / K;
}
// If total time does not exceed H
if (time <= H)
{
ans = K;
high = K - 1;
}
// Otherwise
else
{
low = K + 1;
}
}
// Print the required result
Console.Write(ans);
}
// Driver Code
static public void Main(string []args)
{
int[] arr = { 3, 6, 7, 11 };
int H = 8;
// Function Call
minCollectingSpeed(arr, H);
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach # Function to find the minimum number # of coins to be collected per hour # to empty N piles in H hours def minCollectingSpeed(piles, H): # Stores the minimum coins # to be removed per hour ans = -1 low = 1 # Find the maximum array element high = max(piles) # Perform Binary Search while (low <= high): # Store the mid value of the # range in K K = low + (high - low) // 2 time = 0 # Find the total time taken to # empty N piles by removing K # coins per hour for ai in piles: time += (ai + K - 1) // K # If total time does not exceed H if (time <= H): ans = K high = K - 1 # Otherwise else: low = K + 1 # Print required result print(ans) # Driver Code if __name__ == '__main__': arr = [3, 6, 7, 11] H = 8 # Function Call minCollectingSpeed(arr, H) # This code is contributed by mohit kumar 29
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum number
// of coins to be collected per hour
// to empty N piles in H hours
function minCollectingSpeed(piles, H)
{
// Stores the minimum coins
// to be removed per hour
var ans = -1;
var low = 1, high;
// Find the maximum array element
high = piles.reduce((a,b)=> Math.max(a,b));
// Perform Binary Search
while (low <= high)
{
// Store the mid value of the
// range in K
var K = low + parseInt((high - low) / 2);
var time = 0;
// Find the total time taken to
// empty N piles by removing K
// coins per hour
piles.forEach(ai => {
time += parseInt((ai + K - 1) / K);
});
// If total time does not exceed H
if (time <= H) {
ans = K;
high = K - 1;
}
// Otherwise
else {
low = K + 1;
}
}
// Print the required result
document.write( ans);
}
// Driver Code
var arr = [3, 6, 7, 11];
var H = 8;
// Function Call
minCollectingSpeed(arr, H);
</script>
Producción:
4
Complejidad temporal: O(H*log N)
Espacio auxiliar: O(1)