¿Número mínimo de dinero para que cada elemento de la lista sea mayor o igual a 0?

Lista dada con enteros positivos y negativos. Tenemos que hacer que cada elemento sea mayor o igual a cero. Hay dos tipos de movimientos: primero aumentar todos los elementos en 1 requiere P unidad de dinero, segundo aumentar un elemento en particular en 1 requiere 1 unidad de dinero.

Encuentra la unidad mínima de dinero para hacer que todos los elementos sean mayores o iguales a cero.

Límite de números enteros ( − 10 ) 9 a 10 9

Longitud de la lista - 10 5

Respuestas (1)

¿Por qué no simplemente encontrar el elemento más negativo y aumentar todos los elementos por 1 suficientes veces para llegar a cero? Este es el número mínimo de pasos, aunque puede haber otros caminos igualmente cortos.

Agregado: ahora que se nos da que aumentar todos los elementos cuesta PAG , es mejor aumentar todo mientras haya más de PAG que son negativos. Cuando exactamente PAG son negativos, es un punto de equilibrio, y cuando menos son negativos es más barato aumentarlos individualmente. Así que el nuevo algoritmo es: 1) encontrar el PAG el elemento más negativo. 2) aumentar todo hasta que sea cero 3) aumentar todos los negativos restantes individualmente hasta que lleguen a cero.

Pero el OP quería minimizar el costo de hacer que todos los números no fueran negativos. con la lista ⟨ − 7 , − 2 , − 1 ⟩ , aumentar todo costaría 7 PAG , pero aumentar cada uno individualmente costaría 7 + 2 + 1 Así que si PAG ≤ 10 / 7 su técnica sería más barata, pero si PAG > 10 / 7 el segundo sería más barato. Se vuelve aún más complicado....
@RickDecker: Esa no era parte de la pregunta cuando la respondí. Actualizaré
Lo siento por actualizar la pregunta después de tu respuesta, Ross.
¿Número mínimo de dinero para que cada elemento de la lista sea mayor o igual a 0?
RespuestasAquíPolítica de privacidad1y, 0v