Sie erhalten eine Liste von ( a, b ) und eine Liste von x . Berechnen Sie die maximale Axt + b für jedes x . Sie können annehmen, dass a , b und x nicht negative ganze Zahlen sind.

Ihr Programm oder Funktion muss in erwartet ausgeführt (die Zufälligkeit , wenn Ihr Code das betrifft, nicht der Eingang) O ( n log n ) Zeit , wo n ist die gesamte Eingangslänge (Summe oder Maximum der Längen der beiden Listen).

Das ist Code-Golf. Kürzester Code gewinnt.

Beispiel

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

Ausgabe:

[11 12 14 16 20]

Erläuterung:

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

Anmerkung zur Komplexität:

Wenn Sie ein Builtin mit einer guten durchschnittlichen Komplexität verwendet haben und es randomisiert werden kann, um die erwartete Komplexität theoretisch leicht zu erhalten, können Sie davon ausgehen, dass Ihre Sprache dies getan hat.

Das heißt, wenn Ihr Programm getestet werden kann, um in O ( n log n ) zu sein, möglicherweise mit Ausnahmen in Randbedingungen aufgrund der Implementierung Ihrer Sprache, aber nicht logisch in Ihrem eigenen Code zu sehen, werden wir sagen, es ist O ( n log n ).

Pyth - 99 98 Bytes

Dies ist so ziemlich eine direkte Übersetzung von @ KeithRandalls Python-Antwort. Es kann definitiv viel mehr golfen werden. Ich werde bald eine Erklärung veröffentlichen .

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

Nimmt zwei durch Kommas getrennte Listen auf, die durch Kommas durch stdin getrennt sind.

Probieren Sie es hier aus

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

Berechnet die konvexe Hülle, indem die Eingabe a,bin aufsteigender aReihenfolge durchlaufen wird. Die konvexe Hülle wird im HFormat -1,0,x1,a1,b1,x2,a2,b2,x2,...,xn,an,bnwhere aufgezeichnetxi die x des Schnittes Koordinate a{i-1},b{i-1}und ai,bi.

Dann durchlaufe ich die Eingaben xin sortierter Reihenfolge und schneide die konvexe Hülle ab, um auf dem Laufenden zu bleiben.

Alles ist linear mit Ausnahme der Sorten O (n lgn).

Führen Sie es wie folgt aus:

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

Bearbeiten : Golf viel weiter durch Aktualisieren der konvexen Hülle als Liste (aber mit der gleichen Komplexität wie die ungolfed Version), Verwenden von "split (x + 1)" anstelle von "splitLookup x" und Entfernen aller qualifizierten Funktionsaufrufe wie Predule. foldl.

Dies erzeugt eine Funktion f, die die Liste von (a, b) Paaren und eine Liste von x Werten erwartet. Ich denke, es wird von irgendetwas in der APL-Familie mit den gleichen Ideen in die Länge getrieben, aber hier ist es:

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

Beispielnutzung:

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

Es funktioniert in O (n log n) Zeit; Analyse siehe unten.

Bearbeiten: Hier ist eine ungolfed Version mit der Big-O-Analyse und einer Beschreibung, wie alles funktioniert:

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

Mit einer tatsächlichen binären Suche.

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

Erläuterung

Sei n die Länge von (a, b) und k die Länge von Punkten.

• sortiere (a, b) nach a, dann b - O (n.ln (n))
• Entfernen von Einträgen für doppelte a(parallele Linien) nur die Parallelleitung mit dem maximalen Halt b, die immer größer als die andere sind (wir verhindern Divisionen durch Null , wenn die Berechnung Kreuzungen) - O (n)
• komprimiere das Ergebnis - O (n) : wenn wir aufeinanderfolgende Elemente (a0, b0) (a1, b1) (a2, b2) in der sortierten Liste haben, so dass der Schnittpunkt von (a0, b0) und (a1, b1 ) ist größer als die von (a1, b1) und (a2, b2), dann kann (a1, b1) sicher ignoriert werden.
• eine Liste von (xab) Elementen erstellen, wobei x der Wert ist, bis zu welcher Linie ax + b für x maximal ist (diese Liste ist dank vorheriger Schritte nach x sortiert ) - O (n)

• Erstellen Sie anhand dieser Liste ein Lambda, das eine Intervallprüfung für seine Eingabe durchführt und den Maximalwert berechnet - der Binärbaum wird in O (n) erstellt (siehe /programming//a/4309901/124319 ). Die binäre Suche, die angewendet wird, hat die Komplexität O (ln (n)) . Mit der Beispieleingabe erstellen wir die folgende Funktion (diese Funktion wird dann kompiliert):

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

• wende diese Funktion auf alle Elemente an - O (k.ln (n))

Resultierende Komplexität: O ((n + k) (ln n)) im ungünstigsten Fall.

Wir können keine Komplexitätsschätzung für die Gesamtzahl der Eingaben (n + k) bereitstellen, da k und n unabhängig sind. Wenn beispielsweise n asymptotisch negligeable WRT k , dann wäre die Gesamtkomplexität seine O (k) .

Aber wenn wir annehmen , dass k = O (n) , dann wird die resultierende Komplexität ist O (n.ln (n)) .

Andere Beispiele

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

Und wenn wir die Anführungszeichen verschieben, um zu sehen, was berechnet wird, müssen wir nicht einmal vergleichen (sobald die erste Liste vorverarbeitet ist):

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

Hier ist ein weiteres Beispiel (aus einem Kommentar entnommen):

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

Die effektive Funktion:

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