Dados N montones de plátanos, el i-ésimo montón tiene montones[i] de plátanos y H horas de tiempo hasta que regresen los guardias (N < H). Encuentre el mínimo ( S ) plátanos para comer por hora tal que Koko pueda comerse todos los plátanos dentro de H horas. Cada hora, Koko elige un montón de plátanos y come S plátanos de ese montón. Si la pila tiene menos de S plátanos, los consume todos y no comerá más plátanos durante esa hora.
Ejemplos:
Entrada: montones = [3, 6, 7, 11], H = 8
Salida: 4
Explicación: Koko comerá 4 plátanos por hora para terminar todos los plátanosEntrada: montones = [30, 11, 23, 4, 20], H = 6
Salida: 23
Explicación: Koko comerá 23 plátanos por hora para terminar todos los plátanos
Enfoque ingenuo: Koko debe comer al menos un plátano por hora. Deje que el límite inferior sea start . El número máximo de plátanos que Koko puede comer en una hora es el número máximo de plátanos de todas las pilas. Este es el valor máximo posible de S . Deja que el límite superior termine. Teniendo un intervalo de búsqueda de principio a fin y utilizando la búsqueda lineal, para cada valor de S , se puede verificar si esta velocidad de comer plátanos es válida o no. El primer valor válido de S será la velocidad más lenta y la respuesta deseada.
Complejidad de tiempo: O(N * W), donde W es el máximo de bananas de todas las pilas
Enfoque: el problema dado se puede resolver de manera eficiente mediante el uso de la búsqueda binaria en la técnica de respuesta:
- Cree una función booleana para verificar si la velocidad elegida (plátanos/hora) es suficiente para comer todos los plátanos dentro de H horas dadas o no
- El límite inferior de S es 1 plátano/hora, ya que Koko debe comer un plátano por hora, y el límite superior es el máximo de plátanos de todas las pilas.
- Aplique la búsqueda binaria en el rango de respuesta posible para obtener el valor mínimo de S
- Si la función booleana satisface el valor medio, reduzca más alto a la mitad
- De lo contrario, actualice el límite inferior a la mitad + 1
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
bool check(vector<int>& bananas, int mid_val, int H)
{
int time = 0;
for (int i = 0; i < bananas.size(); i++) {
// to get the ceil value
if (bananas[i] % mid_val != 0) {
// in case of odd number
time += ((bananas[i] / mid_val) + 1);
}
else {
// in case of even number
time += (bananas[i] / mid_val);
}
}
// check if time is less than
// or equals to given hour
if (time <= H) {
return true;
}
else {
return false;
}
}
int minEatingSpeed(vector<int>& piles, int H)
{
// as minimum speed of eating must be 1
int start = 1;
// Maximum speed of eating
// is the maximum bananas in given piles
int end = *max_element(piles.begin(), piles.end());
while (start < end) {
int mid = start + (end - start) / 2;
// Check if the mid(hours) is valid
if ((check(piles, mid, H)) == true) {
// If valid continue to search
// lower speed
end = mid;
}
else {
// If cant finish bananas in given
// hours, then increase the speed
start = mid + 1;
}
}
return end;
}
// Driver code
int main()
{
vector<int> piles = { 30, 11, 23, 4, 20 };
int H = 6;
cout << minEatingSpeed(piles, H);
return 0;
}
Java
// Java implementation for the above approach
import java.util.*;
class GFG{
static boolean check(int[] bananas, int mid_val, int H)
{
int time = 0;
for (int i = 0; i < bananas.length; i++) {
// to get the ceil value
if (bananas[i] % mid_val != 0) {
// in case of odd number
time += ((bananas[i] / mid_val) + 1);
}
else {
// in case of even number
time += (bananas[i] / mid_val);
}
}
// check if time is less than
// or equals to given hour
if (time <= H) {
return true;
}
else {
return false;
}
}
static int minEatingSpeed(int []piles, int H)
{
// as minimum speed of eating must be 1
int start = 1;
// Maximum speed of eating
// is the maximum bananas in given piles
int end = Arrays.stream(piles).max().getAsInt();
while (start < end) {
int mid = start + (end - start) / 2;
// Check if the mid(hours) is valid
if ((check(piles, mid, H)) == true) {
// If valid continue to search
// lower speed
end = mid;
}
else {
// If cant finish bananas in given
// hours, then increase the speed
start = mid + 1;
}
}
return end;
}
// Driver code
public static void main(String[] args)
{
int []piles = { 30, 11, 23, 4, 20 };
int H = 6;
System.out.print(minEatingSpeed(piles, H));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python implementation for the above approach def check(bananas, mid_val, H): time = 0; for i in range(len(bananas)): # to get the ceil value if (bananas[i] % mid_val != 0): # in case of odd number time += bananas[i] // mid_val + 1; else: # in case of even number time += bananas[i] // mid_val # check if time is less than # or equals to given hour if (time <= H): return True; else: return False; def minEatingSpeed(piles, H): # as minimum speed of eating must be 1 start = 1; # Maximum speed of eating # is the maximum bananas in given piles end = sorted(piles.copy(), reverse=True)[0] while (start < end): mid = start + (end - start) // 2; # Check if the mid(hours) is valid if (check(piles, mid, H) == True): # If valid continue to search # lower speed end = mid; else: # If cant finish bananas in given # hours, then increase the speed start = mid + 1; return end; # Driver code piles = [30, 11, 23, 4, 20]; H = 6; print(minEatingSpeed(piles, H)); # This code is contributed by gfgking.
C#
// C# implementation for the above approach
using System;
using System.Linq;
public class GFG{
static bool check(int[] bananas, int mid_val, int H)
{
int time = 0;
for (int i = 0; i < bananas.Length; i++) {
// to get the ceil value
if (bananas[i] % mid_val != 0) {
// in case of odd number
time += ((bananas[i] / mid_val) + 1);
}
else {
// in case of even number
time += (bananas[i] / mid_val);
}
}
// check if time is less than
// or equals to given hour
if (time <= H) {
return true;
}
else {
return false;
}
}
static int minEatingSpeed(int []piles, int H)
{
// as minimum speed of eating must be 1
int start = 1;
// Maximum speed of eating
// is the maximum bananas in given piles
int end = piles.Max();
while (start < end) {
int mid = start + (end - start) / 2;
// Check if the mid(hours) is valid
if ((check(piles, mid, H)) == true) {
// If valid continue to search
// lower speed
end = mid;
}
else {
// If cant finish bananas in given
// hours, then increase the speed
start = mid + 1;
}
}
return end;
}
// Driver code
public static void Main(String[] args)
{
int []piles = { 30, 11, 23, 4, 20 };
int H = 6;
Console.Write(minEatingSpeed(piles, H));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript implementation for the above approach
function check(bananas, mid_val, H) {
let time = 0;
for (let i = 0; i < bananas.length; i++) {
// to get the ceil value
if (bananas[i] % mid_val != 0) {
// in case of odd number
time += Math.floor(bananas[i] / mid_val) + 1;
} else {
// in case of even number
time += Math.floor(bananas[i] / mid_val);
}
}
// check if time is less than
// or equals to given hour
if (time <= H) {
return true;
} else {
return false;
}
}
function minEatingSpeed(piles, H) {
// as minimum speed of eating must be 1
let start = 1;
// Maximum speed of eating
// is the maximum bananas in given piles
let end = [...piles].sort((a, b) => b - a)[0];
while (start < end) {
let mid = start + Math.floor((end - start) / 2);
// Check if the mid(hours) is valid
if (check(piles, mid, H) == true) {
// If valid continue to search
// lower speed
end = mid;
} else {
// If cant finish bananas in given
// hours, then increase the speed
start = mid + 1;
}
}
return end;
}
// Driver code
let piles = [30, 11, 23, 4, 20];
let H = 6;
document.write(minEatingSpeed(piles, H));
</script>
23
Complejidad de tiempo: O(N log W) (W es el máximo de bananas de todas las pilas)
Espacio auxiliar: O(1)