Dado un entero K y una array, height[] donde height[i] denota la altura del i -ésimo árbol en un bosque. La tarea es hacer un corte de altura X desde el suelo tal que se recojan exactamente K unidades de madera. Si no es posible, imprima -1 ; de lo contrario, imprima X.
Ejemplos:
Entrada: altura[] = {1, 2, 1, 2}, K = 2
Salida: 1
Haga un corte en la altura 1, la array actualizada será {1, 1, 1, 1} y
la madera recolectada será { 0, 1, 0, 1} es decir, 0 + 1 + 0 + 1 = 2.Entrada: altura = {1, 1, 2, 2}, K = 1
Salida: -1
Enfoque: este problema se puede resolver mediante la búsqueda binaria .
- Ordenar las alturas de los árboles.
- La altura más baja para hacer el corte es 0 y la altura más alta es la altura máxima entre todos los árboles. Por lo tanto, establezca low = 0 y high = max(height[i]) .
- Repita los pasos a continuación mientras bajo ≤ alto:
- Establecer medio = bajo + ((alto – bajo) / 2) .
- Cuente la cantidad de madera que se puede recolectar si el corte se hace a media altura y guárdelo en una variable recolectada .
- Si recogido = K entonces mid es la respuesta.
- Si recopilado > K , actualice bajo = medio + 1 ya que el corte debe realizarse a una altura superior a la altura actual.
- De lo contrario, actualice high = mid – 1 ya que los cortes deben realizarse a una altura más baja.
- Imprime -1 si no se encuentra tal valor de mid .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Function to return the amount of wood
// collected if the cut is made at height m
int woodCollected(int height[], int n, int m)
{
int sum = 0;
for (int i = n - 1; i >= 0; i--) {
if (height[i] - m <= 0)
break;
sum += (height[i] - m);
}
return sum;
}
// Function that returns Height at
// which cut should be made
int collectKWood(int height[], int n, int k)
{
// Sort the heights of the trees
sort(height, height + n);
// The minimum and the maximum
// cut that can be made
int low = 0, high = height[n - 1];
// Binary search to find the answer
while (low <= high) {
int mid = low + ((high - low) / 2);
// The amount of wood collected
// when cut is made at the mid
int collected = woodCollected(height, n, mid);
// If the current collected wood is
// equal to the required amount
if (collected == k)
return mid;
// If it is more than the required amount
// then the cut needs to be made at a
// height higher than the current height
if (collected > k)
low = mid + 1;
// Else made the cut at a lower height
else
high = mid - 1;
}
return -1;
}
// Driver code
int main()
{
int height[] = { 1, 2, 1, 2 };
int n = sizeof(height) / sizeof(height[0]);
int k = 2;
cout << collectKWood(height, n, k);
return 0;
}
Java
// Java implementation of the approach
import java.util.Arrays;
class GFG
{
static int[] height = new int[]{ 1, 2, 1, 2 };
// Function to return the amount of wood
// collected if the cut is made at height m
public static int woodCollected(int n, int m)
{
int sum = 0;
for (int i = n - 1; i >= 0; i--)
{
if (height[i] - m <= 0)
break;
sum += (height[i] - m);
}
return sum;
}
// Function that returns Height at
// which cut should be made
public static int collectKWood(int n, int k)
{
// Sort the heights of the trees
Arrays.sort(height);
// The minimum and the maximum
// cut that can be made
int low = 0, high = height[n - 1];
// Binary search to find the answer
while (low <= high)
{
int mid = low + ((high - low) / 2);
// The amount of wood collected
// when cut is made at the mid
int collected = woodCollected(n, mid);
// If the current collected wood is
// equal to the required amount
if (collected == k)
return mid;
// If it is more than the required amount
// then the cut needs to be made at a
// height higher than the current height
if (collected > k)
low = mid + 1;
// Else made the cut at a lower height
else
high = mid - 1;
}
return -1;
}
// Driver code
public static void main(String[] args)
{
int k = 2;
int n = height.length;
System.out.print(collectKWood(n,k));
}
}
// This code is contributed by Sanjit_Prasad
Python3
# Python3 implementation of the approach # Function to return the amount of wood # collected if the cut is made at height m def woodCollected(height, n, m): sum = 0 for i in range(n - 1, -1, -1): if (height[i] - m <= 0): break sum += (height[i] - m) return sum # Function that returns Height at # which cut should be made def collectKWood(height, n, k): # Sort the heights of the trees height = sorted(height) # The minimum and the maximum # cut that can be made low = 0 high = height[n - 1] # Binary search to find the answer while (low <= high): mid = low + ((high - low) // 2) # The amount of wood collected # when cut is made at the mid collected = woodCollected(height, n, mid) # If the current collected wood is # equal to the required amount if (collected == k): return mid # If it is more than the required amount # then the cut needs to be made at a # height higher than the current height if (collected > k): low = mid + 1 # Else made the cut at a lower height else: high = mid - 1 return -1 # Driver code height = [1, 2, 1, 2] n = len(height) k = 2 print(collectKWood(height, n, k)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
using System.Collections;
class GFG
{
static int[] height = { 1, 2, 1, 2 };
// Function to return the amount of wood
// collected if the cut is made at height m
public static int woodCollected(int n, int m)
{
int sum = 0;
for (int i = n - 1; i >= 0; i--)
{
if (height[i] - m <= 0)
break;
sum += (height[i] - m);
}
return sum;
}
// Function that returns Height at
// which cut should be made
public static int collectKWood(int n, int k)
{
// Sort the heights of the trees
Array.Sort(height);
// The minimum and the maximum
// cut that can be made
int low = 0, high = height[n - 1];
// Binary search to find the answer
while (low <= high)
{
int mid = low + ((high - low) / 2);
// The amount of wood collected
// when cut is made at the mid
int collected = woodCollected(n, mid);
// If the current collected wood is
// equal to the required amount
if (collected == k)
return mid;
// If it is more than the required amount
// then the cut needs to be made at a
// height higher than the current height
if (collected > k)
low = mid + 1;
// Else made the cut at a lower height
else
high = mid - 1;
}
return -1;
}
// Driver code
public static void Main()
{
int k = 2;
int n = height.Length;
Console.WriteLine(collectKWood(n,k));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation of the approach
// Function to return the amount of wood
// collected if the cut is made at height m
function woodCollected(height, n, m) {
let sum = 0;
for (let i = n - 1; i >= 0; i--) {
if (height[i] - m <= 0)
break;
sum += (height[i] - m);
}
return sum;
}
// Function that returns Height at
// which cut should be made
function collectKWood(height, n, k) {
// Sort the heights of the trees
height.sort((a, b) => a - b);
// The minimum and the maximum
// cut that can be made
let low = 0, high = height[n - 1];
// Binary search to find the answer
while (low <= high) {
let mid = low + ((high - low) / 2);
// The amount of wood collected
// when cut is made at the mid
let collected = woodCollected(height, n, mid);
// If the current collected wood is
// equal to the required amount
if (collected == k)
return mid;
// If it is more than the required amount
// then the cut needs to be made at a
// height higher than the current height
if (collected > k)
low = mid + 1;
// Else made the cut at a lower height
else
high = mid - 1;
}
return -1;
}
// Driver code
let height = [ 1, 2, 1, 2 ];
let n = height.length;
let k = 2;
document.write(collectKWood(height, n, k));
</script>
Producción:
1
Complejidad de tiempo: O (nlog (max_element en la array))
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ashutosh450 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA