Biorąc pod uwagę nieujemną liczbę całkowitą wysokości linii horyzontu, odpowiedz, ile nieprzerwanych pociągnięć pędzla o wysokości 1 jednostki potrzeba do jej pokrycia.

[1,3,2,1,2,1,5,3,3,4,2], wizualizowane jako:

      5    
      5  4 
 3    5334 
 32 2 53342
13212153342

potrzebuje dziewięciu pociągnięć pędzla:

      1    
      2  3 
 4    5555 
 66 7 88888
99999999999

Przykłady

[1,3,2,1,2,1,5,3,3,4,2] → 9

[5,8] → 8

[1,1,1,1] → 1

[] → 0

[0,0] → 0

[2] → 2

[2,0,2] → 4

[10,9,8,9] → 11

JavaScript (Node.js) , 38 bajtów

a=>a.map(v=>(n+=v>p&&v-p,p=v),p=n=0)|n

Wypróbuj online!

Po prostu zachłanny algorytm, który skanuje od lewej do prawej, rysuje linie tylko w razie potrzeby i rysuje tak długo, jak to możliwe.

Dzięki Arnauld, zapisz 2 3 bajty

05AB1E ,  8 7  5 bajtów

Zaoszczędź 2 bajty dzięki @Adnan

0š¥þO

Wypróbuj online!

W jaki sposób?

Korzysta z algorytmu, który został po raz pierwszy znaleziony przez @tsh . Jeśli podoba Ci się ta odpowiedź, pamiętaj, aby głosować również na jej odpowiedź !

Za każdym razem, gdy wieżowiec jest niższy lub tak wysoki jak poprzedni, można go pomalować „za darmo”, po prostu przedłużając pociągnięcia pędzla.

Na przykład malowanie wieżowców $B$ i $C$ na poniższym rysunku nic nie kosztuje.

$E$

W przypadku pierwszego wieżowca zawsze potrzebujemy tyle pociągnięć pędzlem, ile jest w nim podłóg.

Przekształcając to w matematykę:

Jeśli dodamy do listy, można to uprościć:$0$

Skomentował

0š¥þO     # expects a list of non-negative integers  e.g. [10, 9, 8, 9]
0š        # prepend 0 to the list                    -->  [0, 10, 9, 8, 9]
  ¥       # compute deltas                           -->  [10, -1, -1, 1]
   þ      # keep only values made of decimal digits
          # (i.e. without a minus sign)              -->  ["10", "1"]
    O     # sum                                      -->  11

Python 3 , 37 bajtów

lambda a:sum(a)-sum(map(min,a[1:],a))

Wypróbuj online!

_{-5 bajtów, przechodząc na Python 3, dzięki Sarien}

Python 2 , 47 43 42 bajtów

lambda a:sum(a)-sum(map(min,a[1:],a[:-1]))

Wypróbuj online!

Alt:

lambda a:sum(a)-sum(map(min,zip(a[1:],a)))

Wypróbuj online!

Haskell , 32 bajty

(0%)
p%(h:t)=max(h-p)0+h%t
p%_=0

Wypróbuj online!

Ulepszenie rozwiązania Lynn, które śledzi poprzedni element pzamiast patrzeć na następny element. To sprawia, że ​​podstawowy przypadek i połączenie rekurencyjne są krótsze w zamian za konieczność wywołania (0%).

max(h-p)0może być max h p-ptej samej długości.

Haskell , 35 bajtów

f(a:b:c)=max(a-b)0+f(b:c)
f a=sum a

Wypróbuj online!

Linia 2 mogłaby być, f[a]=agdybym nie musiał również zajmować się sprawą [].

K (oK) , 12 7 bajtów

-5 bajtów dzięki ngn!

Port k (oK) rozwiązania 05AB1E Arnaulda (i rozwiązania JavaScript tsh):

+/0|-':

Wypróbuj online!

J , 15 bajtów

Port AJ rozwiązania 05AB1E Arnaulda (i rozwiązania JavaScript tsh):

1#.0>./2-~/\0,]

Wypróbuj online!

Moje naiwne rozwiązanie:

J , 27 bajtów

1#.2(1 0-:])\0,@|:@,~1$~"0]

Wypróbuj online!

Haskell , 34 32 bajty

2 bajty przycięte przez Lynn

g x=sum$max 0<$>zipWith(-)x(0:x)

Wypróbuj online!

Na początek mamy zipWith(-). To zajmuje dwie listy i tworzy nową listę różnic między nimi. Następnie łączymy to z xi (0:x). (0:)jest funkcją, która dodaje zero na początku listy i łącząc ją z zipWith(-), uzyskujemy różnice między kolejnymi elementami tej listy z zerami na początku listy. Następnie zamieniamy wszystkie ujemne na zero za pomocą (max 0<$>). Spowoduje to utworzenie nowej listy, w której każdy element jest liczbą nowych pociągnięć, które należy rozpocząć w każdej wieży. Aby uzyskać sumę, sumujemy je sum.

Japt , 8 bajtów

-2 bajty z @Shaggy

mîT Õ¸¸è

Wyjaśnienie

mîT Õ¸¸è      Full program. Implicit input U
                e.g. U = [2,0,2]
mîT             Map each item X and repeat T(0) X times
                     U = ["00","","00"]
    Õ           Transpose rows with columns
                     U = ["0 0","0 0"]
     ¸¸         Join using space and then split in space
                     U = ["0","0","0","0"]
        è       Return the count of the truthy values

Wypróbuj online!

MATL , 8 bajtów

0whd3Y%s

Wypróbuj online!

Prawie algorytm @ Arnaulda. Zapisano jeden bajt (dzięki @LuisMendo), przesyłając uint64zamiast wybierania )pozytywnych wpisów.

Galaretka , 5 bajtów

Port mojej odpowiedzi 05AB1E , która sama w sobie jest podobna do @tsh JS answer .

ŻI0»S

Wypróbuj online!

Skomentował

ŻI0»S    - main link, expecting a list of non-negative integers  e.g. [10, 9, 8, 9]
Ż        - prepend 0                                             -->  [0, 10, 9, 8, 9]
 I       - compute the deltas                                    -->  [10, -1, -1, 1]
  0»     - compute max(0, v) for each term v                     -->  [10, 0, 0, 1]
    S    - sum                                                   -->  11

Japt , 7 6 bajtów

änT fq

Spróbuj

1 bajt zapisany dzięki Oliverowi.

änT xwT    :Implicit input of integer array
än         :Consecutive differences / Deltas
  T        :  After first prepending 0
    f      :Filter elements by
     q     :  Square root (The square root of a negative being NaN)
           :Implicitly reduce by addition and output

R , 30 bajtów

sum(pmax(0,diff(c(0,scan()))))

Wypróbuj online!

Przenoszenie rozwiązania @Arnauld, które z kolei wywodzi się z doskonałego rozwiązania @tsh

Retina 0.8.2 , 21 bajtów

\d+
$*
(1+)(?=,\1)

1

Wypróbuj online! Link zawiera przypadki testowe. Wyjaśnienie:

\d+
$*

Konwertuj na unary.

(1+)(?=,\1)

Usuń wszystkie zakładki z następną wieżą, które nie wymagają nowego pociągnięcia.

1

Policz pozostałe pociągnięcia.

Common Lisp, 88 87 bajtów

(lambda(s)(let((o 0))(dolist(c s)(incf o(max 0 c))(mapl(lambda(y)(decf(car y)c))s))o))

nie zminimalizowane

(lambda (skyline)
  (let ((output 0))
    (dolist (current-skyscraper-height skyline)
      (incf output (max 0 current-skyscraper-height))
      (mapl (lambda (skyscraper)
              (decf (car skyscraper) current-skyscraper-height))
            skyline))
    output)))

Sprawdź to

Po pomalowaniu jednej wieży potrzeba kilku pociągnięć pędzla równych jej wysokości. Te pociągnięcia pędzla przekładają się na wszystkie następujące, o czym tutaj chodzi, odejmując wysokość bieżącej wieży od wszystkich innych wież (i samej, ale to nie ma znaczenia). Jeśli kolejna wieża jest krótsza, zostanie przesunięta do liczby ujemnej, a ta liczba ujemna zostanie następnie odjęta od kolejnych wież (wskazując pociągnięcia pędzla, których nie można było przetłumaczyć z poprzedniej wieży na następne). W rzeczywistości po prostu odejmuje liczbę od wszystkich wysokości wieży, w tym poprzednich, ale to nie ma znaczenia, ponieważ nie patrzymy ponownie na poprzednie.

05AB1E , 13 10 bajtów

Z>Lε@γPO}O

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

Z            # Get the maximum of the (implicit) input-list
 >           # Increase it by 1 (if the list only contains 0s)
  L          # Create a list in the range [1, max]
   ε         # Map each value to:
    @        #  Check if this value is >= for each value in the (implicit) input
     γ       #  Split into chunks of adjacent equal digits
      P      #  Take the product of each inner list
       O     #  Take the sum
        }O   # And after the map: take the sum (which is output implicitly)

C # (interaktywny kompilator Visual C #) z flagą /u:System.Math, 47 bajtów

n=>n.Select((a,i)=>i<1?a:Max(a-n[i-1],0)).Sum()

Wypróbuj online!

Stara wersja, z flagą /u:System.Math, 63 bajty

n=>n.Aggregate((0,0),(a,b)=>(a.Item1+Max(0,b-a.Item2),b)).Item1

Wydaje mi się, że to rozwiązanie jest bardziej eleganckie niż pierwsze. Przechodzi przez tablicę z krotką o dwóch wartościach jako wartością początkową, zbierając wartości i przechowuje wartość przed nią w drugiej części krotki.

Wypróbuj online!

Pyth, 8 bajtów

s>#0.++0

Kolejny port cudownej odpowiedzi @ tsh . Pobiera sumę ( s) dodatnich wartości ( >#0) delt (. +) Danych wejściowych z 0 poprzedzonymi ( +0Q, wywnioskowano końcowe Q).

Spróbuj go online tutaj , lub sprawdzić wszystkie przypadki testowe od razu tutaj .

Metoda łączenia ciągów, 10 bajtów

To było rozwiązanie, które napisałem przed przeglądaniem innych odpowiedzi.

lcj.t+d*LN

Zestaw testowy.

lcj.t+d*LNQ   Implicit: Q=eval(input()), b=<newline>, N=<quote mark>
              Trailing Q inferred
        L Q   Map each element of Q...
       * N    ... to N repeated that many times
     +b       Prepend a newline
   .t         Transpose, padding with spaces
  j           Join on newlines
 c            Split on whitespace
l             Take the length, implicit print

Clojure, 50 bajtów

#((reduce(fn[[s n]i][(+(max(- i n)0)s)i])[0 0]%)0)

Wypróbuj online! (Dlaczego nic nie drukuje?)

#( ; begin anonymous function
    (reduce
        (fn [[s n] i] ; internal anonymous reducing function, destructures accumulator argument into a sum and the previous item
            [(+ (max (- i n) 0) s ; the sum part of the accumulator becomes the previous sum plus the larger of zero and the difference between the current number and the last one, which is how many new strokes need to be started at this point
            i]) ; ...and the previous item part becomes the current item
        [0 0] ; the initial value of the accumulator gives no strokes yet, and nothing for them to cover yet
        %) ; reduce over the argument to the function
    0) ; and get the sum element of the last value of the accumulator.

Java (JDK) , 57 bajtów

a->{int s=0,p=0;for(int x:a)s-=(x>p?p:x)-(p=x);return s;}

Wypróbuj online!

Kolejny port TSH „s Javascript odpowiedź . Upewnij się więc, że ich oceniłeś.

Zauważ, że użyłem odejmowania zamiast dodawania, ponieważ pozwoliło mi to napisać (p=x)jako poprawny operand w tej samej instrukcji.

MATL , 15 14 13 bajtów

ts:<~"@Y'x]vs

Dane wejściowe to wektor kolumny, używany ;jako separator.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

t       % Implicit input: column vector. Duplicate
s       % Sum
:       % Range from 1 to that. Gives a row vector
<~      % Greater or equal? Element-wise with broadcast
"       % For each column
  @     %   Push current columnn
  Y'    %   Run-length encoding. Gives vector of values (0, 1) and vector of lengths
  x     %   Delete vector of lengths
]       % End
v       % Vertically concatenate. May give an empty array
s       % Sum. Implicit display

Perl 5, 21 bajtów

$\+=$_>$'&&$_-$';//}{

TIO

W jaki sposób

• -p+ }{+ $\trik
• //dopasowuje pusty ciąg, aby w następnym wierszu postmatch $'zawierał poprzedni wiersz
• $\+=$_>$'&&$_-$'aby kumulować różnicę między bieżącą linią a poprzednią, jeśli prąd jest większy niż poprzedni (można również zapisać $\+=$_-$' if$_>$', ale Perl nie analizuje $\+=$_-$'if$_>$'tego samego)

Stax , 8 bajtów

Φ┐Γ╟φφ.╨

Uruchom i debuguj

Wykorzystuje powszechnie stosowane podejście z rozwiązania JavaScript tsh.

Wolfram Language (Mathematica) , 34 bajty

Port @Arnauld „s rozwiązania .

Tr@Select[{##,0}-{0,##},#>0&]&@@#&

Wypróbuj online!