Comencemos con la siguiente observación:
Deje que max denote el máximo de la secuencia a1,...,an , y deje que min denote su mínimo. Si a1=max , entonces elegir b1=b2=...=bn=⌊(max+min)/2⌋ es óptimo.
¿Por qué es este el caso? Bueno, dado que la secuencia comienza con el máximo, elegimos grande y sufrimos una gran desviación del mínimo de la secuencia (ya que cualquier posterior debe ser mayor o igual a ), o elegimos pequeño y sufrimos desviación al . El promedio minimiza la desviación máxima.b1bib1b1max
Ahora podemos tratar de generalizar esta observación para usarla en secuencias generales . Por ejemplo, podemos dividir cualquier secuencia en subsecuencias, de modo que cada una comience con el máximo de la subsecuencia respectiva.a1,...,an
Ejemplo: se divide en , y .(2,6,4,1,5,2,8,7,5,1)(2)(6,4,1,5,2)(8,7,5,1)
Dada esta partición, ahora podemos resolver cada una de estas subsecuencias por separado, y obtener una asignación de los 's, que sin embargo podrían violar la condición no decreciente. Esto se puede solucionar sin perder la optimización.bi
Observe que la última subsecuencia siempre contiene el máximo de toda la secuencia (de lo contrario, habría otra subsecuencia después de ella). Sean los valores que asignamos a las subsecuencias. Ahora, para lograr una no disminución en , comenzamos desde atrás en y hacia el frente. Si es mayor que , simplemente establecemos . Si es más pequeño, lo guardamos. Luego, procedemos a comparar con y así sucesivamente. Tenga en cuenta que reducir al valor demaxw1,w2,...,wkkw1,...,wkwkwk−1wkwk−1:=wkwk−2wk−1wiwi+1nunca aumenta la desviación, ya que el valor máximo en la subsecuencia asignada con es siempre menor que el máximo en la subsecuencia asignada con .wiwi+1
Este algoritmo debería ser correcto, creo. Con respecto al tiempo de ejecución, el paso clave es calcular los máximos crecientes para las subsecuencias, que es posible en ? No sabe dónde contribuye.O(n)l
Creo que esto debería ser factible en O (n).
Tome el problema similar: dado , 1 ≤ i ≤ n, y d ≥ 0, encuentre en orden no descendente tal que para todo i, o demuestre que no es posible. Esto se puede hacer en O (n), y utilizando la búsqueda binaria, el problema original se resuelve en O (n log l).b i | a i - b i | ≤ dai bi |ai−bi|≤d
Ahora si hay i ≤ j tal que a_i - a_j> 2d, entonces no hay solución (porque ).bi≥ai−d,bj≤aj+d<ai−2d+d=ai−d≤bi
Pero si a_i - a_j ≤ 2d para todo i ≤ j, entonces creo que siempre se encontrará una solución. Entonces, todo lo que tenemos que hacer es encontrar m = max (a_i - a_j) para todo i ≤ j, y elegir d = floor ((m + 1) / 2). Ese máximo se puede encontrar en O (n).
fuente