Diberikan daftar tinggi bilangan bulat langit-langit non-negatif, jawab berapa banyak sapuan kuas horisontal 1 unit tinggi yang tidak terputus yang diperlukan untuk menutupinya.
[1,3,2,1,2,1,5,3,3,4,2]
, divisualisasikan sebagai:
5
5 4
3 5334
32 2 53342
13212153342
membutuhkan sembilan sapuan kuas:
1
2 3
4 5555
66 7 88888
99999999999
Contohnya
[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
Jawaban:
JavaScript (Node.js) , 38 byte
Cobalah online!
Cukup algoritma serakah yang memindai dari kiri ke kanan, hanya menggambar garis jika diperlukan, dan menggambarnya selama mungkin.
Terima kasih Arnauld, simpan
23 bytesumber
05AB1E ,
8 75 byteDisimpan 2 byte berkat @Adnan
Cobalah online!
Bagaimana?
Ini menggunakan algoritma yang pertama kali ditemukan oleh @tsh . Jika Anda menyukai jawaban ini, pastikan untuk membatalkan jawaban mereka juga!
Setiap kali gedung pencakar langit lebih rendah dari atau setinggi yang sebelumnya, itu dapat dicat 'gratis' hanya dengan memperpanjang sapuan kuas.
Misalnya, mengecat gedung pencakar langitB dan C pada gambar di bawah ini tidak ada biaya.
Di sisi lain, kita perlu 2 sapuan kuas baru untuk mengecat gedung pencakar langitE , tidak peduli apakah itu akan digunakan kembali setelah itu atau tidak.
Untuk gedung pencakar langit pertama, kita selalu membutuhkan sapuan kuas sebanyak lantai.
Mengubah ini menjadi matematika:
Jika kita menambahkan ke daftar, ini dapat disederhanakan menjadi:0
Berkomentar
sumber
0š¥ʒd}O
menghemat satu byte.ʒd}
denganþ
harus menghemat dua byte.Python 3 , 37 byte
Cobalah online!
-5 byte dengan beralih ke Python 3, terima kasih kepada Sarien
Python 2 ,
474342 byteCobalah online!
Alt:
Cobalah online!
sumber
Haskell , 32 byte
Cobalah online!
Peningkatan pada solusi Lynn yang melacak elemen sebelumnya
p
alih-alih melihat elemen berikutnya. Hal ini membuat kasing dasar dan panggilan rekursif menjadi lebih pendek sebagai ganti kebutuhan untuk memanggil(0%)
.max(h-p)0
bisamax h p-p
dengan panjang yang sama.sumber
Haskell , 35 byte
Cobalah online!
Baris 2 bisa jadi
f[a]=a
jika saya juga tidak harus menangani kasus ini[]
.sumber
K (oK) ,
127 byte-5 byte terima kasih kepada ngn!
Sebuah k (oK) pelabuhan solusi 05AB1E Arnauld (dan solusi JavaScript TSH ini):
Cobalah online!
J , 15 byte
Port AJ dari solusi 05AB1E Arnauld (dan solusi JavaScript tsh):
Cobalah online!
Solusi naif saya:
J , 27 byte
Cobalah online!
sumber
':
) menggunakan elemen identitas implisit (0
untuk-
) sebelum daftar, jadi0,
tidak perlu. Anda dapat menghilangkan{
x}
untuk membuatnya komposisi:+/0|-':
Some primitive verbs result in a different special-cased initial value: +, *, - and & are provided with 0, 1, 0 or the first element of the sequence, respectively
Haskell ,
3432 byte2 byte dipangkas oleh Lynn
Cobalah online!
Jadi untuk memulai kita sudah
zipWith(-)
. Ini mengambil dua daftar dan menghasilkan daftar baru dari perbedaan berpasangan mereka. Kami kemudian menggabungkannya denganx
dan(0:x)
.(0:)
adalah fungsi yang menambahkan nol di bagian depan daftar dan dengan menggabungkannya denganzipWith(-)
kita mendapatkan perbedaan antara elemen berturut-turut dari daftar itu dengan nol di depan. Lalu kita mengubah semua yang negatif menjadi nol dengan(max 0<$>)
. Ini membuat daftar baru di mana setiap elemen adalah jumlah pukulan baru yang harus dimulai di setiap menara. Untuk mendapatkan total, kami hanya menjumlahkannya dengansum
.sumber
g x=sum$max 0<$>zipWith(-)x(0:x)
adalah 32 byte :)sum.zipWith((max 0.).(-))<*>(0:)
.
memiliki prioritas lebih tinggi daripada<*>
.Japt , 8 byte
-2 byte dari @Shaggy
Penjelasan
Cobalah online!
sumber
mîT Õ¸¸è
A.y()
's padding, by the way.MATL , 8 byte
Cobalah online!
Algoritma @ Arnauld cukup banyak. Disimpan satu byte (terima kasih @LuisMendo) dengan melakukan casting
uint64
daripada memilih)
entri positif.sumber
Jelly , 5 byte
Port jawaban 05AB1E saya , yang mirip dengan jawaban JS @tsh .
Cobalah online!
Berkomentar
sumber
Japt ,
76 byteCobalah
1 byte disimpan berkat Oliver.
sumber
R , 30 byte
Cobalah online!
Porting solusi @Arnauld yang pada gilirannya berasal dari solusi hebat @tsh
sumber
Retina 0.8.2 , 21 byte
Cobalah online! Tautan termasuk kasus uji. Penjelasan:
Konversikan ke unary.
Hapus semua tumpang tindih dengan menara berikutnya, yang tidak memerlukan stroke baru.
Hitung goresan yang tersisa.
sumber
Common Lisp,
8887 bytenon-minified
Menguji
Ketika satu menara dicat, dibutuhkan sejumlah sapuan kuas yang sama dengan tingginya. Sapuan kuas ini diterjemahkan ke semua yang berikut, yang ditunjukkan di sini dengan mengurangi ketinggian menara saat ini dari semua menara lainnya (dan itu sendiri, tapi itu tidak masalah). Jika menara berikut lebih pendek, maka akan didorong ke angka negatif, dan angka negatif ini kemudian akan dikurangi dari menara yang mengikuti (menunjukkan sapuan kuas yang tidak dapat diterjemahkan dari menara sebelumnya ke yang berikutnya). Ini sebenarnya hanya mengurangi jumlah dari semua ketinggian menara, termasuk yang sebelumnya, tetapi ini tidak masalah karena kita tidak melihat yang sebelumnya lagi.
sumber
05AB1E ,
1310 byteCobalah secara online atau verifikasi semua kasus uji .
Penjelasan:
sumber
C # (Visual C # Interactive Compiler) dengan flag
/u:System.Math
, 47 byteCobalah online!
Versi lama, dengan flag
/u:System.Math
, 63 byteSaya merasa solusi ini lebih elegan dari yang pertama. Itu pergi melalui array dengan tuple dua nilai sebagai nilai awal, mengambil nilai, dan menyimpan nilai sebelum itu di bagian kedua tuple.
Cobalah online!
sumber
Pyth, 8 byte
Namun port lain dari jawaban luar biasa @ tsh . Mengambil jumlah (
s
) dari nilai positif (>#0
) dari delta (. +) Dari input dengan 0 prepended (+0Q
, trailing Q disimpulkan).Coba online di sini , atau verifikasi semua uji sekaligus di sini .
Metode penggabungan string, 10 byte
Ini adalah solusi yang saya tulis sebelum menelusuri jawaban lainnya.
Suite uji.
sumber
Clojure, 50 byte
Cobalah online! (Mengapa ini tidak mencetak apa-apa?)
sumber
Java (JDK) , 57 byte
Cobalah online!
Port lain dari TSH 's Javascript jawabannya . Jadi, pastikan Anda telah memutakhirkannya.
Perhatikan bahwa saya menggunakan pengurangan bukannya penambahan karena memungkinkan saya untuk menulis
(p=x)
sebagai operan yang benar dalam pernyataan yang sama.sumber
MATL ,
151413 byteInput adalah vektor kolom, menggunakan
;
sebagai pemisah.Cobalah online! Atau verifikasi semua kasus uji .
Penjelasan
sumber
Perl 5, 21 byte
TIO
Bagaimana
-p
+}{
+$\
trik//
cocok dengan string kosong sehingga untuk postmatch baris berikutnya$'
akan berisi baris sebelumnya$\+=$_>$'&&$_-$'
untuk mengakumulasi perbedaan antara baris saat ini dan sebelumnya jika saat ini lebih besar dari sebelumnya, (bisa juga ditulis$\+=$_-$' if$_>$'
, tetapi perl tidak menguraikan$\+=$_-$'if$_>$'
yang sama)sumber
Stax , 8 byte
Jalankan dan debug itu
Menggunakan pendekatan yang banyak digunakan dari solusi JavaScript tsh.
sumber
Bahasa Wolfram (Mathematica) , 34 byte
Sebuah port dari @Arnauld 's solusi .
Cobalah online!
sumber