Delta suma máxima: ¿Cómo podría ordenar 1 millón de enteros, de un conjunto de enteros positivos infinitos que tienen como máximo 8 dígitos de largo, de modo que estén (1) ordenados, y (2) la suma de todos los deltas entre números adyacentes es en el valor máximo posible y por qué?

Answer 1

Estoy complementando la respuesta correcta de Alex Kritchevsky.

Curiosamente, hay dos interpretaciones para esta pregunta (si la diferencia considerada es de valor absoluto o no), y para ambos la respuesta es la misma. Una forma limpia de abordar este problema es aplicar algo de aritmética. Tenga en cuenta que realmente desea maximizar (N = 10 ^ 6)

[matemáticas] S = | x_2 – x_1 | + | x_3 – x_2 | + \ puntos + | x_N – x_ {N – 1} | [/ matemática]

pero, porque [matemáticas] x_i \ leq x_ {i + 1} [/ matemáticas], [matemáticas] | x_ {i + 1} – x_i | = x_ {i + 1} – x_i [/ ​​math], entonces

[matemáticas]
\ begin {array} {ll}
S & = (x_2 – x_1) + (x_3 – x_2) +… + (x_N – x_ {N – 1}) \\\\
& = x_N – x_1
\ end {array}
[/matemáticas]

[observe que esto combina las dos interpretaciones]

y, al final, puede elegir x [2..N-1] arbitrariamente, porque los únicos términos que importan son x [1] yx [N]. Dado eso, la forma obvia de maximizar S es x [1] = 10 ^ 7 yx [N] = 10 ^ 9 – 1 y el problema se resuelve con S = 10 ^ 9 – 10 ^ 7 – 1, y el resto de los números se pueden elegir de la forma que desee.

Answer 2

El delta total más alto que puede obtener es igual al número entero de 8 dígitos más alto menos el más bajo, o 99999999 – 10000000 = 89,999,999.
Entonces, solo use 999,999 copias de 10 millones y una copia de 99,999,999 como su lista.
Si tienen que ser únicos, use los primeros números 999,999 y luego 99,999,999.