Dada una array wood[] de tamaño N , que representa la longitud de N piezas de madera y un número entero K , se deben cortar al menos K piezas de la misma longitud de las piezas de madera dadas. La tarea es encontrar la máxima longitud posible de estas K piezas de madera que se pueden obtener.
Ejemplos:
Entrada: madera[] = {5, 9, 7}, K = 3
Salida: 5
Explicación:
Cortar arr[0] = 5 = 5
Cortar arr[1] = 9 = 5 + 4
Cortar arr[2] = 7 = 5 + 2
Por lo tanto, la longitud máxima que se puede obtener cortando la madera en 3 piezas es 5.Entrada: madera[] = {5, 9, 7}, K = 4
Salida: 4
Explicación:
Cortar arr[0] = 5 = 4 + 1
Cortar arr[1] = 9 = 2 * 4 + 1
Cortar arr[2 ] = 7 = 4 + 3
Por lo tanto, la longitud máxima que se puede obtener cortando la madera en 4 pedazos es 4.
Enfoque: El problema se puede resolver mediante una búsqueda binaria . Siga los pasos a continuación para resolver el problema:
- Encuentre el elemento máximo de la array wood[] y guárdelo en una variable, digamos Max .
- El valor de L debe estar en el rango [1, Max] . Por lo tanto, aplique la búsqueda binaria en el rango [1, Max] .
- Inicialice dos variables, digamos, izquierda = 1 y derecha = Max para almacenar el rango en el que se encuentra el valor de L.
- Compruebe si es posible cortar la madera en K piezas con una longitud de cada pieza igual a (izquierda + derecha) / 2 o no. Si se determina que es cierto, actualice left = (left + right) / 2 .
- De lo contrario, actualice right = (left + right) / 2 .
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 check if it is possible to cut
// woods into K pieces of length len
bool isValid(int wood[], int N, int len, int K)
{
// Stores count of pieces
// having length equal to K
int count = 0;
// Traverse wood[] array
for (int i = 0; i < N; i++) {
// Update count
count += wood[i] / len;
}
return count >= K;
}
// Function to find the maximum value of L
int findMaxLen(int wood[], int N, int K)
{
// Stores minimum possible value of L
int left = 1;
// Stores maximum possible value of L
int right = *max_element(wood,
wood + N);
// Apply binary search over
// the range [left, right]
while (left <= right) {
// Stores mid value of
// left and right
int mid = left + (right - left) / 2;
// If it is possible to cut woods
// into K pieces having length
// of each piece equal to mid
if (isValid(wood, N, mid,
K)) {
// Update left
left = mid + 1;
}
else {
// Update right
right = mid - 1;
}
}
return right;
}
// Driver Code
int main()
{
int wood[] = { 5, 9, 7 };
int N = sizeof(wood) / sizeof(wood[0]);
int K = 4;
cout << findMaxLen(wood, N, K);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to check if it is possible
// to cut woods into K pieces of
// length len
static boolean isValid(int wood[], int N,
int len, int K)
{
// Stores count of pieces
// having length equal to K
int count = 0;
// Traverse wood[] array
for(int i = 0; i < N; i++)
{
// Update count
count += wood[i] / len;
}
return count >= K;
}
// Function to find the maximum value of L
static int findMaxLen(int wood[], int N,
int K)
{
// Stores minimum possible value of L
int left = 1;
// Stores maximum possible value of L
int right = Arrays.stream(wood).max().getAsInt();
// Apply binary search over
// the range [left, right]
while (left <= right)
{
// Stores mid value of
// left and right
int mid = left + (right - left) / 2;
// If it is possible to cut woods
// into K pieces having length
// of each piece equal to mid
if (isValid(wood, N, mid, K))
{
// Update left
left = mid + 1;
}
else
{
// Update right
right = mid - 1;
}
}
return right;
}
// Driver Code
public static void main(String[] args)
{
int wood[] = { 5, 9, 7 };
int N = wood.length;
int K = 4;
System.out.print(findMaxLen(wood, N, K));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program to implement # the above approach # Function to check if it is possible to # cut woods into K pieces of length len def isValid(wood, N, len, K): # Stores count of pieces # having length equal to K count = 0 # Traverse wood[] array for i in range(N): # Update count count += wood[i] // len return (count >= K) # Function to find the maximum value of L def findMaxLen(wood, N, K): # Stores minimum possible value of L left = 1 # Stores maximum possible value of L right = max(wood) # Apply binary search over # the range [left, right] while (left <= right): # Stores mid value of # left and right mid = left + (right - left) // 2 # If it is possible to cut woods # into K pieces having length # of each piece equal to mid if (isValid(wood, N, mid, K)): # Update left left = mid + 1 else: # Update right right = mid - 1 return right # Driver Code if __name__ == '__main__': wood = [ 5, 9, 7 ] N = len(wood) K = 4 print(findMaxLen(wood, N, K)) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
using System.Linq;
class GFG{
// Function to check if it is possible
// to cut woods into K pieces of
// length len
static bool isValid(int []wood, int N,
int len, int K)
{
// Stores count of pieces
// having length equal to K
int count = 0;
// Traverse wood[] array
for(int i = 0; i < N; i++)
{
// Update count
count += wood[i] / len;
}
return count >= K;
}
// Function to find the maximum
// value of L
static int findMaxLen(int []wood,
int N, int K)
{
// Stores minimum possible
// value of L
int left = 1;
// Stores maximum possible
// value of L
int right = wood.Max();
// Apply binary search over
// the range [left, right]
while (left <= right)
{
// Stores mid value of
// left and right
int mid = left +
(right - left) / 2;
// If it is possible to cut woods
// into K pieces having length
// of each piece equal to mid
if (isValid(wood, N,
mid, K))
{
// Update left
left = mid + 1;
}
else
{
// Update right
right = mid - 1;
}
}
return right;
}
// Driver Code
public static void Main(String[] args)
{
int []wood = {5, 9, 7};
int N = wood.Length;
int K = 4;
Console.Write(findMaxLen(wood,
N, K));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to check if it is possible
// to cut woods into K pieces of
// length len
function isValid(wood , N , len , K) {
// Stores count of pieces
// having length equal to K
var count = 0;
// Traverse wood array
for (i = 0; i < N; i++) {
// Update count
count += parseInt(wood[i] / len);
}
return count >= K;
}
// Function to find the maximum value of L
function findMaxLen(wood , N , K) {
// Stores minimum possible value of L
var left = 1;
// Stores maximum possible value of L
var right = Math.max.apply(Math,wood);
// Apply binary search over
// the range [left, right]
while (left <= right) {
// Stores mid value of
// left and right
var mid = left + (right - left) / 2;
// If it is possible to cut woods
// into K pieces having length
// of each piece equal to mid
if (isValid(wood, N, mid, K)) {
// Update left
left = mid + 1;
} else {
// Update right
right = mid - 1;
}
}
return right;
}
// Driver Code
var wood = [ 5, 9, 7 ];
var N = wood.length;
var K = 4;
document.write(findMaxLen(wood, N, K));
// This code is contributed by todaysgaurav
</script>
Producción:
4
Complejidad de tiempo: O(N * Log 2 M), donde M es el elemento máximo de la array dada
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por RohitOberoi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA