Se le da una lista de ( a, b ) y una lista de x . Calcule el máximo ax + b para cada x . Se puede suponer una , b y x son números enteros no negativos.

Su programa o función debe ejecutarse en el tiempo esperado (al azar si su código involucra eso, no la entrada) O ( n log n ) tiempo donde n es la longitud de entrada total (suma o máximo de las longitudes de ambas listas).

Este es el código de golf. El código más corto gana.

Ejemplo

[[2 8] [4 0] [2 1] [1 10] [3 3] [0 4]] [1 2 3 4 5]

Salida:

[11 12 14 16 20]

Explicación:

11 = 1*1 + 10
12 = 1*2 + 10 = 2*2 + 8
14 = 2*3 + 8
16 = 2*4 + 8 = 4*4 + 0
20 = 4*5 + 0

Nota sobre la complejidad:

Si usó un incorporado que tiene una buena complejidad de caso promedio, y puede ser aleatorizado para obtener la complejidad esperada fácilmente en teoría, puede asumir que su idioma lo hizo.

Eso significa que, si se puede probar que su programa está en O ( n log n ), posiblemente con excepciones de casos extremos debido a la implementación de su lenguaje, pero no se puede ver lógicamente en su propio código, diremos que es O ( n log n ).

Pyth - 99 98 bytes

Esta es más o menos una traducción directa de la respuesta de Python de @ KeithRandall. Definitivamente se puede jugar mucho más al golf. Publicaré una explicación pronto .

K[_1Z;FNShQAkdNW&>K2>+*k@K_3d+*@K_2@K_3eK=K<K_3)~K[c-eKd-k@K_2kd;FNSeQW&>K2>N@K2=K>K3)aY+*hKN@K1;Y

Toma dos listas delimitadas por comas, separadas por comas mediante stdin.

Pruébalo aquí

K                  K=
 [  )              A List containing
  _1               Negative 1
  Z                Zero
FN                 For N in
 ShQ               Sorted first input
Akd                Double assign k and d
 N                 To N
 W                 While
  &                Logical And
   >K2             K>2
   >               Greater Than
    +*k@K_3d       K[-3]*k+d
    +              Plus
     *@K_2@K_3     K[-2]*K[-3]
     eK            K[-1]
  =K               K=
   <K_3            K[:-3]
  )                Close while loop
 ~K                K+=
  [      )         List constructor
   c               Float division
    -              Minus
     eK            K[-1]
     d             d
    -              Minus
     k             k
     @K_2          K[-2]
   k               k
   d               d
 ;                 End list and for loop
FN                 For N in
  SeQ              Sorted second input
  W                While loop
   &               Logical and
    >K2            K[2:]
    >              Greater than
     N             N
     @K2           K[2]
   =K              K=
   >K3             K[3:]
  )                Close while loop
  aY               Y.append - Y is empty list
   +               Plus
    *hKN           (K+1)*N
    @K1            K[1]
;                  Close out everything
Y                  Print Y

Python, 214 bytes

S=sorted
def M(L,X):
 H=[-1,0];R={}
 for a,b in S(L):
    while H[2:]and a*H[-3]+b>H[-2]*H[-3]+H[-1]:H=H[:-3]
    H+=[1.*(H[-1]-b)/(a-H[-2]),a,b]
 for x in S(X):
    while H[2:]and x>H[2]:H=H[3:]
    R[x]=H[0]*x+H[1]
 return R

Calcula el casco convexo iterando a través de la entrada a,ben aorden creciente . El casco convexo se registra Hutilizando el formato -1,0,x1,a1,b1,x2,a2,b2,x2,...,xn,an,bndonde xies la coordenada x de la intersección de a{i-1},b{i-1}y ai,bi.

Luego itero a través de la entrada xs en orden ordenado, truncando el casco convexo para mantener el ritmo a medida que avanzo.

Todo es lineal excepto los tipos que son O (n lgn).

Ejecútalo como:

>>> print M([[2,8],[4,0],[2,1],[1,10],[3,3],[0,4]], [1,2,3,4,5])
{1: 11, 2: 12, 3: 14, 4: 16, 5: 20}

Haskell, 204 271 bytes

Editar : jugó mucho más al actualizar el casco convexo como una lista (pero con la misma complejidad que la versión sin golf), usando "split (x + 1)" en lugar de "splitLookup x", y eliminando todas las llamadas a funciones calificadas como Predule. pliegue

Esto crea una función f que espera la lista de pares (a, b) y una lista de valores x. Supongo que cualquier miembro de la familia APL lo dejará boquiabierto con las mismas ideas, pero aquí va:

import Data.Map
r=fromListWith max
[]%v=[(0,v)]
i@((p,u):j)%v|p>v#u=j%v|0<1=(v#u,v):i
(a,b)#(c,d)=1+div(b-d)(c-a)
o i x=(\(a,b)->a*x+b)$snd$findMax$fst$split(x+1)$r$foldl'(%)[]$r$zip(fmap fst i)i
f=fmap.o

Uso de la muestra:

[1 of 1] Compiling Main             ( linear-min.hs, interpreted )
Ok, modules loaded: Main.
λ> f [(2,8), (4,0), (2,1), (1,10), (3,3), (0,4)] [1..5]
[11,12,14,16,20]
λ> f [(1,20), (2,12), (3,11), (4,8)] [1..5]
[21,22,23,24,28]

Funciona en tiempo O (n log n); ver abajo para el análisis.

Editar: Aquí hay una versión sin golf con el análisis big-O y una descripción de cómo funciona todo:

import Prelude hiding (null, empty)
import Data.Map hiding (map, foldl)

-- Just for clarity:
type X = Int
type Y = Int
type Line = (Int,Int)
type Hull = Data.Map.Map X Line
slope (a,b) = a

{-- Take a list of pairs (a,b) representing lines a*x + b and sort by
    ascending slope, dropping any lines which are parallel to but below
    another line.

    This composition is O(n log n); n for traversing the input and
    the output, log n per item for dictionary inserts during construction.
    The input and output are both lists of length <= n.
--}
sort :: [Line] -> [Line]
sort = toList . fromListWith max

{-- For lines ax+b, a'x+b' with a < a', find the first value of x
    at which a'x + b' exceeds ax + b. --}
breakEven :: Line -> Line -> X
breakEven p@(a,b) q@(a',b') = if slope p < slope q
                                 then 1 + ((b - b') `div` (a' - a))
                                 else error "unexpected ordering"

{-- Update the convex hull with a line whose slope is greater
    than any other lines in the hull.  Drop line segments
    from the hull until the new line intersects the final segment.
    split is used to find the portion of the convex hull
    to the right of some x value; it has complexity O(log n).
    insert is also O(log n), so one invocation of this 
    function has an O(log n) cost.

    updateHull is recursive, but see analysis for hull to
    account for all updateHull calls during one execution.
--}
updateHull :: Line -> Hull -> Hull
updateHull line hull
    | null hull = singleton 0 line
    | slope line <= slope lastLine = error "Hull must be updated with lines of increasing slope"
    | hull == hull' = insert x line hull
    | otherwise = updateHull line hull''
    where (lastBkpt, lastLine) = findMax hull
          x = breakEven lastLine line
          hull' = fst $ x `split` hull
          hull'' = fst $ lastBkpt `split` hull

{-- Build the convex hull by adding lines one at a time,
    ordered by increasing slope.

    Each call to updateHull has an immediate cost of O(log n),
    and either adds or removes a segment from the hull. No
    segment is added more than once, so the total cost is
    O(n log n).
--}
hull :: [Line] -> Hull
hull = foldl (flip updateHull) empty . sort

{-- Find the highest line for the given x value by looking up the nearest
    (breakpoint, line) pair with breakpoint <= x.  This uses the neat
    function splitLookup which looks up a key k in a dictionary and returns
    a triple of:
        - The subdictionary with keys < k.
        - Just v if (k -> v) is in the dictionary, or Nothing otherwise
        - The subdictionary with keys > k.

    O(log n) for dictionary lookup.
--}
valueOn :: Hull -> X -> Y
valueOn boundary x = a*x + b
    where (a,b) = case splitLookup x boundary of
                    (_  , Just ab, _) -> ab
                    (lhs,       _, _) -> snd $ findMax lhs


{-- Solve the problem!

    O(n log n) since it maps an O(log n) function over a list of size O(n).
    Computation of the function to map is also O(n log n) due to the use
    of hull.
--}
solve :: [Line] -> [X] -> [Y]
solve lines = map (valueOn $ hull lines)

-- Test case from the original problem
test = [(2,8), (4,0), (2,1), (1,10), (3,3), (0,4)] :: [Line]
verify = solve test [1..5] == [11,12,14,16,20]

-- Test case from comment
test' = [(1,20),(2,12),(3,11),(4,8)] :: [Line]
verify' = solve test' [1..5] == [21,22,23,24,28]

Lisp común - 648 692

Con una búsqueda binaria real.

(use-package :optima)(defun z(l e)(labels((i(n m)(/(-(cadr m)(cadr n))(-(car n)(car m))))(m(l)(match l((list* a b c r)(if(<(i a b)(i b c))(list* a(m(list* b c r)))(m(list* a c r))))(_ l)))(f(x &aux(x(cdr x)))`(+(*,(car x)x),(cadr x)))(g(s e)(let*((q(- e s))(h(+ s(floor q 2)))d)(if(> q 1)(let((v(g s h))(d(pop l)))`(if(< x,(car d)),v,(g(1+ h)e)))(cond((not(car (setq d (pop l))))(f d))((> q 0)`(if(< x,(car d)),(f d),(f(pop l))))(t(f d)))))))(setq l(loop for(a b)on(m(remove-duplicates(#3=stable-sort(#3# l'< :key'cadr)'< :key'car):key 'car)) by #'cdr collect`(,(when b(i a b)),(car a),(cadr a))))`(mapcar(eval(lambda(x),(g 0(1-(length l)))))',e)))

(z '((2 8) (4 0) (2 1) (1 10) (3 3) (0 4)) '(1 2 3 4 5))
=> (11 12 14 16 20)

Explicación

Sea n la longitud de (a, b) yk la longitud de los puntos.

• ordenar (a, b) por a, luego b - O (n.ln (n))
• eliminar entradas para duplicados a(líneas paralelas), conservando solo la línea paralela con el máximo b, que siempre es mayor que la otra (evitamos divisiones por cero al calcular las intersecciones) - O (n)
• comprima el resultado - O (n) : cuando tenemos elementos consecutivos (a0, b0) (a1, b1) (a2, b2) en la lista ordenada, de modo que el punto de intersección de (a0, b0) y (a1, b1 ) es mayor que la de (a1, b1) y (a2, b2), entonces (a1, b1) puede ignorarse de forma segura.
• construya una lista de elementos (xab), donde x es el valor hasta el cual la línea ax + b es máxima para x (esta lista está ordenada por x gracias a los pasos anteriores) - O (n)

• dada esa lista, construya una lambda que realice una comprobación de intervalo para su entrada y calcule el valor máximo: el árbol binario está construido en O (n) (consulte /programming//a/4309901/124319 ). La búsqueda binaria que se aplicará tiene una complejidad O (ln (n)) . Con la entrada de ejemplo, creamos la siguiente función (esa función se compila luego):

  (LAMBDA (X)
    (IF (< X 4)
        (IF (< X 2)
            (IF (< X -6)
                (+ (* 0 X) 4)
                (+ (* 1 X) 10))
            (+ (* 2 X) 8))
        (+ (* 4 X) 0)))
  

• aplicar esa función para todos los elementos - O (k.ln (n))

Complejidad resultante: O ((n + k) (ln n))) en el peor de los casos.

No podemos proporcionar una estimación de complejidad para el número total de entradas (n + k), porque k y n son independientes. Por ejemplo, si n es wrt k asintóticamente negligente , entonces la complejidad total sería O (k) .

Pero si suponemos que k = O (n) , entonces la complejidad resultante es O (n.ln (n)) .

Otros ejemplos

(z '((1 10) (1 8) (1 7)) '(1 2 3 4 5))
=> (11 12 13 14 15)

Y si retrocedemos las citas para ver qué se está calculando, podemos ver que ni siquiera necesitamos hacer ninguna comparación (una vez que la primera lista está preprocesada):

(MAPCAR (LAMBDA (X) (+ (* 1 X) 10)) '(1 2 3 4 5))

Aquí hay otro ejemplo (tomado de un comentario):

(z '((1 20) (2 12) (3 11) (4 8)) '(1 2 3 4 5))
=> (21 22 23 24 28)

La función efectiva:

(MAPCAR
  (LAMBDA (X)
    (IF (< X 4)
        (+ (* 1 X) 20)
        (+ (* 4 X) 8)))
  '(1 2 3 4 5))