Valor a restar de los elementos de la array para que la suma de todos los elementos sea igual a K

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:
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: 
    1. Establecer medio = bajo + ((alto – bajo) / 2) .
    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 .
    3. Si recogido = K entonces mid es la respuesta.
    4. Si recopilado > K , actualice bajo = medio + 1 ya que el corte debe realizarse a una altura superior a la altura actual.
    5. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *