Вам предоставляется список ( a, b ) и список x . Вычислить максимальный топор + б для каждого х . Можно предположить, что a , b и x являются неотрицательными целыми числами.

Ваша программа или функция должны выполняться в ожидаемом (случайном порядке, если ваш код включает это, а не во вводе) O ( n log n ) время, где n - общая длина ввода (сумма или максимум длин обоих списков).

Это код-гольф. Самый короткий код выигрывает.

пример

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

Выход:

[11 12 14 16 20]

Объяснение:

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

Примечание о сложности:

Если вы использовали встроенную систему, имеющую хорошую сложность в среднем случае, и ее можно рандомизировать, чтобы легко получить ожидаемую сложность в теории, вы можете предположить, что ваш язык сделал это.

Это означает, что если ваша программа может быть проверена на O ( n log n ), возможно, с исключениями в крайнем случае из-за реализации вашего языка, но не может быть логически видна в вашем собственном коде, мы скажем, что это O ( n log n ).

Pyth - 99 98 байт

Это в значительной степени прямой перевод ответа @ KeithRandall's Python. Это определенно может быть гораздо больше. Я скоро опубликую объяснение .

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

Принимает два списка через запятую, разделенных запятыми через стандартный ввод.

Попробуй здесь

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 байтов

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

Вычисляет выпуклую оболочку путем перебора входных данных a,bв возрастающем aпорядке. Выпуклая оболочка записывается в Hформате -1,0,x1,a1,b1,x2,a2,b2,x2,...,xn,an,bnгде xiкоордината x пересечения a{i-1},b{i-1}и ai,bi.

Затем я перебираю входные данные xв отсортированном порядке, обрезая выпуклую оболочку, чтобы идти в ногу со временем.

Все линейно, кроме сортов O (n lgn).

Запустите это как:

>>> 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 байт

Редактирование : значительно улучшило игру, обновив выпуклый корпус в виде списка (но с той же сложностью, что и в версии без гольфа), используя «split (x + 1)» вместо «splitLookup x» и удалив все квалифицированные вызовы функций, такие как Predule. foldl.

Это создает функцию f, которая ожидает список пар (a, b) и список значений x. Я думаю, что все члены семейства APL сдувают его по длине, используя те же идеи, но здесь это так:

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

Пример использования:

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

Работает за O (n log n) времени; см. ниже для анализа.

Редактировать: вот версия без гольфа с анализом big-O и описанием того, как все это работает:

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

С реальным бинарным поиском.

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

объяснение

Пусть n - длина (a, b), а k - длина точек.

• сортировать (a, b) по a, затем b - O (n.ln (n))
• удалить записи для дубликатов a(параллельные линии), сохраняя только параллельную линию с максимумом b, который всегда больше другого (мы предотвращаем деление на ноль при вычислении пересечений) - O (n)
• сжать результат - O (n) : когда у нас есть последовательные элементы (a0, b0) (a1, b1) (a2, b2) в отсортированном списке, так что точка пересечения (a0, b0) и (a1, b1) ) больше, чем один из (a1, b1) и (a2, b2), тогда (a1, b1) можно смело игнорировать.
• построить список (xab) элементов, где x - значение, до которого строка ax + b максимальна для x (этот список отсортирован по x благодаря предыдущим шагам) - O (n)

• исходя из этого списка, создайте лямбду, которая выполняет интервальную проверку своего ввода и вычисляет максимальное значение - двоичное дерево построено в O (n) (см. /programming//a/4309901/124319 ). Применяемый двоичный поиск имеет сложность O (ln (n)) . На примере ввода мы строим следующую функцию (эта функция затем компилируется):

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

• применить эту функцию для всех элементов - O (k.ln (n))

Результирующая сложность: O ((n + k) (ln n))) в худшем случае.

Мы не можем предоставить оценку сложности для общего количества входов (n + k), потому что k и n не зависят. Например, если n асимптотически пренебрежимо мало по отношению к k , то общая сложность будет O (k) .

Но если мы предположим, что k = O (n) , то получаем сложность O (n.ln (n)) .

Другие примеры

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

И если мы переместим обратные кавычки, чтобы посмотреть, что вычисляется, мы увидим, что нам даже не нужно ничего сравнивать (после предварительной обработки первого списка):

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

Вот еще один пример (взят из комментария):

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

Эффективная функция:

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