Saltar al contenido

La altura de la sierra

Enunciado

A Filomena, que es guardabosques, le encargaron metros metros de madera del monte que cuida, y ella puso la condición: no se tumba ni un árbol. La cuadrilla trae una sierra que se fija a una altura, recorre el monte entero y se lleva todo lo que sobresalga de esa altura. Un árbol de 20 metros con la sierra en 15 deja 5 metros de madera. Uno de 10 metros no deja nada, porque la sierra le pasa por encima sin tocarlo. Mientras más alta se fije la sierra, menos madera sale, y a Filomena le importa dejar el monte lo más entero que pueda. Quiere la altura más alta con la que todavía junte los metros del encargo.

Escribe una función que reciba arboles, una lista de enteros positivos con la altura de cada árbol (al menos uno, en cualquier orden), y metros, un entero positivo que nunca pasa de la suma de todas las alturas. Regresa un entero: la altura más alta, en metros enteros, con la que la madera cortada llega o pasa los metros del encargo.

Con árboles de 20, 15, 10 y 17 metros y un encargo de 7, la respuesta es 15: salen 5 del primero y 2 del último, que son justo los 7. Con la sierra en 16 saldrían 4 y 1, o sea 5, y el encargo se queda corto.

La altura 0 siempre sirve, porque con la sierra en el suelo sale el monte completo: con dos árboles de 5 metros y un encargo de 10, la respuesta es 0.

No te sirve repartir el encargo entre los árboles: el corte es el mismo para todos y los árboles bajos no ponen nada. Las alturas llegan a mil millones y hay montes de hasta 60 árboles, así que subir la sierra metro por metro tampoco termina.

Ejemplos

  • El ejemplo

    [20, 15, 10, 17], 7 → 15

  • La sierra en el suelo

    [5, 5], 10 → 0

  • Cinco árboles de dos cifras

    [4, 42, 40, 26, 46], 20 → 36

  • Un solo árbol

    [100], 30 → 70

  • Un metro de madera

    [20, 15, 10, 17], 1 → 19

Además de estas, el reto tiene pruebas ocultas que se revelan al enviar tu solución.

Empiezas con esto

Python

def altura_corte(arboles, metros):
    pass

JavaScript

function alturaCorte(arboles, metros) {
}
Resolver este reto

Se abre en el navegador, con el editor y las pruebas. Este reto es del plan completo; los de O(1) y O(log n) son gratis.

Más retos de O(n log n)

Ver todos los retos →