Vous obtenez une liste de ( a, b ) et une liste de x . Calculez la hache maximale + b pour chaque x . Vous pouvez supposer que a , b et x sont des entiers non négatifs.

Votre programme ou fonction doit s'exécuter dans le temps prévu (au hasard si votre code implique cela, pas l'entrée) O ( n log n ) temps où n est la longueur totale d'entrée (somme ou maximum des longueurs des deux listes).

C'est du code-golf. Le code le plus court gagne.

Exemple

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

Production:

[11 12 14 16 20]

Explication:

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

Remarque sur la complexité:

Si vous avez utilisé un module intégré ayant une bonne complexité de cas moyen, et qu'il peut être randomisé pour obtenir facilement la complexité attendue en théorie, vous pouvez supposer que votre langage l'a fait.

Cela signifie que si votre programme peut être testé pour être en O ( n log n ), peut-être avec des exceptions de cas limites en raison de l'implémentation de votre langage, mais ne peut pas être vu logiquement dans votre propre code, nous dirons que c'est O ( n log n ).

Pyth - 99 98 octets

Ceci est à peu près une traduction directe de la réponse Python de @ KeithRandall. Il peut certainement être joué beaucoup plus. Je posterai bientôt une explication .

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

Prend deux listes séparées par des virgules, séparées par des virgules via stdin.

Essayez-le ici

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 octets

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

Calcule la coque convexe en itérant à travers l'entrée a,ben aordre croissant . La coque convexe est enregistrée en Hutilisant le format -1,0,x1,a1,b1,x2,a2,b2,x2,...,xn,an,bnoù xiest la coordonnée x de l'intersection de a{i-1},b{i-1}etai,bi .

Ensuite, je répète si l'entrée x en ordre trié, tronquant la coque convexe pour suivre le rythme.

Tout est linéaire sauf les sortes qui sont O (n lgn).

Exécutez-le comme:

>>> 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 octets

Edit : a joué beaucoup plus loin en mettant à jour la coque convexe sous forme de liste (mais avec la même complexité que la version non golfée), en utilisant "split (x + 1)" au lieu de "splitLookup x", et en supprimant tous les appels de fonction qualifiés comme Predule. foldl.

Cela crée une fonction f qui attend la liste des paires (a, b) et une liste de valeurs x. Je suppose que tout dans la famille APL sera emporté par la longueur en utilisant les mêmes idées, mais voici:

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

Exemple d'utilisation:

[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]

Il fonctionne en temps O (n log n); voir ci-dessous pour l'analyse.

Edit: Voici une version non golfée avec l'analyse big-O et une description de la façon dont tout cela fonctionne:

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 commun - 648 692

Avec une recherche binaire réelle.

(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)

Explication

Soit n la longueur de (a, b) et k la longueur des points.

• trier (a, b) par a, puis b - O (n.ln (n))
• supprimer les entrées pour les doublons a(lignes parallèles), en ne conservant que la ligne parallèle avec le maximum b, qui est toujours supérieur à l'autre (on évite les divisions par zéro lors du calcul des intersections) - O (n)
• compresser le résultat - O (n) : lorsque nous avons des éléments consécutifs (a0, b0) (a1, b1) (a2, b2) dans la liste triée, de sorte que le point d'intersection de (a0, b0) et (a1, b1 ) est supérieur à celui de (a1, b1) et (a2, b2), alors (a1, b1) peut être ignoré en toute sécurité.
• construire une liste d'éléments (xab), où x est la valeur jusqu'à laquelle la ligne ax + b est maximale pour x (cette liste est triée par x grâce aux étapes précédentes) - O (n)

• étant donné cette liste, créez un lambda qui effectue une vérification d'intervalle pour son entrée et calcule la valeur maximale - l'arborescence binaire est construite en O (n) (voir /programming//a/4309901/124319 ). La recherche binaire qui sera appliquée a une complexité O (ln (n)) . Avec l'exemple d'entrée, nous construisons la fonction suivante (cette fonction est ensuite compilée):

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

• appliquer cette fonction pour tous les éléments - O (k.ln (n))

Complexité résultante: O ((n + k) (ln n))) dans le pire des cas.

Nous ne pouvons pas fournir d'estimation de complexité pour le nombre total d'entrées (n + k), car k et n sont indépendants. Par exemple, si n est asymptotiquement négligeable par rapport à k , alors la complexité totale serait O (k) .

Mais si nous supposons que k = O (n) , alors la complexité résultante est O (n.ln (n)) .

Autres exemples

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

Et si nous déplaçons les guillemets arrière pour voir ce qui est calculé, nous pouvons voir que nous n'avons même pas besoin de faire de comparaison (une fois que la première liste est prétraitée):

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

Voici un autre exemple (tiré d'un commentaire):

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

La fonction efficace:

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