Dividir un número entre N números para que tengan la menor diferencia posible entre ellos

Question

Digamos que tengo los números 2, 3, 0 y quiero repartir el número 4 entre ellos con el objetivo de que sean lo más iguales posible.

El resultado en el caso anterior sería: 3, 3, 3. Le damos el 1 al 2 y el 3 al 0 y ahora hemos agotado nuestro 4 y hemos hecho los números lo más iguales posible.

Si tuviéramos 2, 3, 0 y repartiéramos 5 entre ellos, el resultado sería 3,3, 3,3, 3,3.

Si tuviéramos 2, 3, 0 y 1 para dividir, el resultado sería 2, 3, 1.

Si tuviéramos 5, 7 y 4 para repartir, el resultado sería 8, 8.

etc.

Necesito esto para un juego que estoy haciendo en el que hay una cuadrícula y un líquido se extiende por igual a las baldosas de la cuadrícula. Traté de jugar con la división y las proporciones, pero estoy en la oscuridad para ser honesto.

Answer 1

Digamos que empiezas con $x,y,z$ y el número que se añade es $a$ . Después de añadir $a$ el líquido total será $x+y+z+a$ y el líquido medio por baldosa es $(x+y+z+a)/3$ . Tus ejemplos parecen indicar que no puedes quitar líquido de ninguna baldosa, sólo añadir, por lo que puedes conseguir una distribución uniforme de $(x+y+z+a)/3$ por baldosa siempre que $(x+y+z+a)/3 \geq \max(x,y,z)$ .

Ahora bien, si $(x+y+z+a)/3<\max(x,y,z)$ Entonces no podemos conseguir una distribución uniforme porque (al menos) una de las baldosas ya tiene demasiado líquido. Así que $z=\max(x,y,z)$ (simplemente reordénalos si no es el caso). Entonces no queremos añadir nada a $z$ puesto que ya supera la media $(x+y+z+a)/3$ . Así que vamos a tratar de hacer $x$ y $y$ lo más uniforme posible. El líquido total en esos dos azulejos después de añadir $a$ será $x+y+a$ y la media es $(x+y+a)/2$ . Podemos conseguir un reparto equitativo si $(x+y+a)/2 \geq \max(x,y)$ .

Por lo demás, $(x+y+a)/2 <\max(x,y)$ , por lo que una de las dos baldosas restantes ya tiene demasiado líquido. Digamos que $y=\max(x,y)$ (de nuevo, reordénalos si no es el caso). Entonces no queremos añadir nada a $y$ Así que simplemente añadimos todo el líquido a $x$ .

En resumen: digamos que los importes son $x,y,z$ donde $x \leq y \leq z$ y añadimos la cantidad $a$ .

• Si $(x+y+z+a)/3 \geq \max(x,y,z)=z$ podemos distribuir uniformemente el líquido para terminar con $(x+y+z+a)/3$ en cada baldosa.
• Si $(x+y+z+a)/3< \max(x,y,z)=z$ pero $(x+y+a)/2 \geq \max(x,y)=y$ entonces no añadimos nada a $z$ y distribuimos uniformemente el líquido entre $x$ y $y$ para conseguir $(x+y+a)/2$ en cada uno.
• Si $(x+y+z+a)/3< \max(x,y,z)=z$ y $(x+y+a)/2 < \max(x,y)=y$ , entonces añadimos todo el líquido a $x$ para conseguir $x+a$ y nos vamos $y$ y $z$ solo.

Answer 2

Es decir, un algoritmo de fuerza bruta consiste en mantener un array con todos los números, y aumentar siempre el número más bajo en 1 hasta que no quede nada por aumentar. ¿Es esto demasiado lento para su aplicación?

Una forma más rápida es ordenar todos los números y, empezando por el 2º más pequeño, calcular cuánto total habrá que sumar a todos los números menores que éste para que todos sean iguales. Una vez que se llega al número cuya suma es mayor que el número que hay que repartir, se puede rellenar.

Ejemplo

1 2 3 4 5, hay que distribuir 4

^--------

2 2 3 4 5, hay que distribuir 3

--^------

3 3 4 5, hay que distribuir 1

----^----

4 3 3 4 5, hay que distribuir 0

Hecho