Otrzymujesz listę ( a, b ) i listę x . Oblicz maksymalne ax + b dla każdego x . Możesz założyć , że a , b i x są liczbami całkowitymi nieujemnymi.

Twój program lub funkcja musi działać w oczekiwanym (losowym przypadku, jeśli Twój kod tego wymaga, a nie na wejściu) O ( n log n ) czas, gdzie n jest całkowitą długością wejściową (sumą lub maksymalną długością obu list).

To jest golf golfowy. Najkrótszy kod wygrywa.

Przykład

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

Wynik:

[11 12 14 16 20]

Wyjaśnienie:

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

Uwaga na temat złożoności:

Jeśli użyłeś wbudowanego programu o dobrej złożoności średnich przypadków i można go randomizować, aby łatwo uzyskać oczekiwaną złożoność w teorii, możesz założyć, że Twój język to zrobił.

Oznacza to, że jeśli twój program może być przetestowany pod kątem O ( n log n ), być może z wyjątkami wielkości liter z powodu implementacji twojego języka, ale nie można go logicznie zobaczyć we własnym kodzie, powiemy, że to O ( n log n ).

Pyth - 99 98 bajtów

Jest to prawie bezpośrednie tłumaczenie odpowiedzi Python @ KeithRandall. Zdecydowanie więcej można w nią grać w golfa. Wkrótce opublikuję wyjaśnienie .

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

Pobiera dwie listy rozdzielane przecinkami, oddzielone przecinkami przez standardowe wejście.

Wypróbuj tutaj

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 bajtów

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

Oblicza wypukły kadłub poprzez iterację wprowadzanych danych a,bw akolejności rosnącej . Wypukły kadłub jest rejestrowany w Hformacie, w -1,0,x1,a1,b1,x2,a2,b2,x2,...,xn,an,bnktórym xijest współrzędną x przecięcia a{i-1},b{i-1}i ai,bi.

Następnie iteruję dane wejściowe xw posortowanej kolejności, obcinając wypukły kadłub, aby nadążać.

Wszystko jest liniowe, z wyjątkiem rodzajów, które są O (n lgn).

Uruchom to jak:

>>> 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 bajtów

Edycja : grał znacznie dalej, aktualizując wypukły kadłub jako listę (ale z taką samą złożonością jak wersja nie golfowa), używając „split (x + 1)” zamiast „splitLookup x” i usuwając wszystkie kwalifikowane wywołania funkcji, takie jak Predule. złożyć

Tworzy to funkcję f, która oczekuje listy par (a, b) i listy wartości x. Wydaje mi się, że wszystko to w rodzinie APL zostanie zdumione, używając tych samych pomysłów, ale oto:

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

Przykładowe użycie:

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

Działa w czasie O (n log n); analiza poniżej.

Edycja: Oto wersja bez golfa z analizą big-O i opisem tego, jak to wszystko działa:

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]

Common Lisp - 648 692

Z rzeczywistym wyszukiwaniem binarnym.

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

Wyjaśnienie

Niech n będzie długością (a, b), a k długością punktów.

• sortuj (a, b) według a, a następnie b - O (n.ln (n))
• usuń wpisy dla duplikatów a(linie równoległe), zachowując tylko linię równoległą z maksimum b, która jest zawsze większa od drugiej (zapobiegamy podziałom przez zero przy obliczaniu skrzyżowań) - O (n)
• kompresuj wynik - O (n) : gdy mamy posortowane elementy (a0, b0) (a1, b1) (a2, b2) na posortowanej liście, tak że punkt przecięcia (a0, b0) i (a1, b1 ) jest większy niż jeden z (a1, b1) i (a2, b2), wówczas (a1, b1) można bezpiecznie zignorować.
• zbuduj listę elementów (xab), gdzie x jest wartością do której linii ax + b jest maksymalna dla x (ta lista jest posortowana według x dzięki poprzednim krokom) - O (n)

• biorąc pod uwagę tę listę, zbuduj lambda, która sprawdza interwał dla danych wejściowych i oblicza maksymalną wartość - drzewo binarne jest wbudowane w O (n) (patrz /programming//a/4309901/124319 ). Wyszukiwanie binarne, które zostanie zastosowane, ma złożoność O (ln (n)) . Za pomocą przykładowego wejścia budujemy następującą funkcję (ta funkcja jest następnie kompilowana):

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

• zastosuj tę funkcję do wszystkich elementów - O (k.ln (n))

Wynikająca z tego złożoność: O ((n + k) (ln n))) w najgorszym przypadku.

Nie możemy podać oszacowania złożoności dla całkowitej liczby danych wejściowych (n + k), ponieważ k i n są niezależne. Na przykład, jeśli n jest asymptotycznie pomijalnym wrt k , wówczas całkowita złożoność wynosiłaby O (k) .

Ale jeśli założymy, że k = O (n) , to złożoność wynikowa to O (n.ln (n)) .

Inne przykłady

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

A jeśli przeniesiemy cudzysłowy, aby zobaczyć, co jest obliczane, możemy zobaczyć, że nie musimy nawet dokonywać żadnych porównań (po przetworzeniu pierwszej listy):

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

Oto kolejny przykład (wzięty z komentarza):

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

Skuteczna funkcja:

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