Koko Eating Bananas

Q: Berapa kompleksitas waktu Koko Eating Bananas?

Pencarian biner berjalan dalam waktu O(n log m) , dengan n sebagai jumlah tumpukan dan m sebagai tumpukan terbesar: sekitar log2(m) pemeriksaan, 30 saat m = 10^9 , dan setiap pemeriksaan membaca semua tumpukan satu kali. Ruang tambahan yang digunakan adalah O(1) .

Q: Apa batas bawah dan batas atas untuk kecepatannya?

Batas atas adalah tumpukan terbesar: pada batas ini, setiap tumpukan membutuhkan satu jam, dan itu selalu cukup. Batas bawahnya adalah 1, dan kamu bisa menaikkannya menjadi jumlah total pisang dibagi h , dibulatkan ke atas, karena Koko makan paling banyak k pisang per jam.

Q: Bagaimana cara membagi bilangan bulat dan membulatkan hasilnya ke atas?

Gunakan (p + k-1) / k dengan pembagian bilangan bulat. Menambahkan k-1 mendorong sisa apa pun melewati kelipatan k berikutnya, sedangkan kelipatan yang tepat tetap sama: 10 dengan kecepatan 4 menghasilkan 13 / 4 = 3 , dan 8 menghasilkan 11 / 4 = 2 . Tidak perlu menggunakan bilangan floating-point.

SedangBinary search

+10

Koko memiliki n tumpukan pisang, dengan piles[i] pisang di tumpukan i, dan h jam. Dia memilih kecepatan makan k, berupa bilangan bulat pisang per jam, lalu mempertahankannya. Setiap jam dia makan k pisang dari satu tumpukan. Jika tersisa kurang dari k pisang di tumpukan itu, dia menghabiskannya lalu beristirahat sampai jam tersebut berakhir. Kembalikan nilai k terkecil yang memungkinkannya menghabiskan semua tumpukan dalam waktu paling lama h jam.

Fungsi

minEatingSpeed(piles: integer-array, h: integer) → integer

pilesinteger-array: jumlah pisang di setiap tumpukan
hinteger: jumlah jam yang dimiliki Koko
Mengembalikaninteger: kecepatan makan bilangan bulat terkecil, dalam satuan pisang per jam, yang menghabiskan setiap tumpukan dalam h jam

Batasan

1 ≤ piles.length ≤ 5000
1 ≤ piles[i] ≤ 10⁹
piles.length ≤ h ≤ 10⁹, jadi selalu ada jawaban.

Contoh

Input: piles = [4, 10, 7, 3]h = 6
Output: 5
Penjelasan: Pada kecepatan 5, tumpukan 4, 10, 7, dan 3 membutuhkan waktu 1, 2, 2, dan 1 jam: totalnya 6 jam, sesuai batas waktu. Pada kecepatan 4, tumpukan tersebut membutuhkan waktu 1, 3, 2, dan 1 jam, totalnya 7 jam.

Pertanyaan lanjutan

Soal Koko: Koko menghabiskan seluruh tumpukan secara berurutan, paling banyak k pisang per hari, dalam d hari. Berapa nilai k terkecil, dan apa yang berubah dalam pencarianmu?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Jawabannya adalah kecepatan, bukan posisi dalam array, dan hal itu menyamarkan pencarian biner. Memeriksa satu kecepatan membutuhkan satu kali melewati tumpukan, dan jika kecepatan k selesai tepat waktu, semua kecepatan yang lebih tinggi juga akan selesai tepat waktu. Jadi, lakukan pencarian biner pada kecepatan dari 1 hingga tumpukan terbesar: sekitar 30 pemeriksaan, bukan hingga satu miliar.

Coba setiap kecepatan mulai dari 1

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Koko tidak pernah berpindah ke tumpukan lain dalam waktu satu jam, jadi tumpukan berisi p pisang membutuhkan p / k jam, dibulatkan ke atas: dengan kecepatan 4, 10 pisang membutuhkan 3 jam. Coba kecepatan 1, 2, 3, dan seterusnya, lalu kembalikan kecepatan pertama yang total waktunya tidak melebihi h. Itulah kecepatan terkecil karena semua kecepatan yang lebih lambat gagal, dan perulangan berhenti pada kecepatan sebesar tumpukan terbesar, saat setiap tumpukan membutuhkan satu jam.

Dengan m sebagai tumpukan terbesar, ada hingga m pemeriksaan untuk n tumpukan: sekitar 5 × 10^12 langkah untuk 5000 tumpukan yang ukurannya mendekati 10^9 dan h = 5000.

Algoritma

Atur speed = 1.
Hitung jam pada kecepatan ini: untuk setiap tumpukan, tambahkan (pile + speed-1) / speed dengan menggunakan total 64-bit.
Jika totalnya paling banyak h, kembalikan speed.
Jika tidak, tambahkan 1 ke speed lalu hitung lagi.

def minEatingSpeed(piles, h):
    speed = 1
    while True:
        hours = 0
        for pile in piles:
            hours += (pile + speed - 1) // speed  # a started pile costs a whole hour
        if hours <= h:
            return speed
        speed += 1

Pencarian biner berdasarkan kecepatan

Intuisi

Saat kecepatannya meningkat, setiap tumpukan membutuhkan jumlah jam yang sama atau lebih sedikit, jadi jawaban untuk pertanyaan "apakah kecepatan ini menyelesaikannya tepat waktu?" akan berbunyi tidak, tidak, tidak, lalu ya mulai dari jawabannya. Binary search menemukan ya yang pertama.

Pertahankan rentang lo hingga hi yang selalu mencakup jawaban, dimulai dari 1 dan tumpukan terbesar, yang kecepatannya membutuhkan satu jam per tumpukan sehingga cukup. Jika kecepatan tengah mid cukup, jawabannya adalah mid atau lebih lambat, jadi tetapkan hi = mid. Jika tidak, semua kecepatan yang lebih lambat juga gagal, jadi tetapkan lo = mid + 1. Saat lo bertemu dengan hi, itulah jawabannya.

Pada contoh pertama, rentangnya dimulai dari 1 hingga 10. Kecepatan 5 cukup, jadi rentangnya menjadi 1 hingga 5; kecepatan 3 membutuhkan 10 jam, jadi rentangnya menjadi 4 hingga 5; kecepatan 4 membutuhkan 7 jam, jadi rentangnya menjadi 5 hingga 5.

Algoritma

Tetapkan lo = 1 dan hi ke tumpukan terbesar.
Selama lo < hi, ambil mid = lo + (hi - lo) / 2.
Hitung jumlah jam pada kecepatan mid: tambahkan (pile + mid-1) / mid untuk setiap tumpukan, dengan total 64-bit.
Jika totalnya paling banyak h, tetapkan hi = mid; jika tidak, tetapkan lo = mid + 1.
Kembalikan lo.

def minEatingSpeed(piles, h):
    lo, hi = 1, max(piles)  # the largest pile always works: one hour per pile
    while lo < hi:
        mid = lo + (hi - lo) // 2
        hours = 0
        for pile in piles:
            hours += (pile + mid - 1) // mid
        if hours <= h:
            hi = mid  # mid works, so the answer is mid or slower
        else:
            lo = mid + 1  # mid is too slow, so the answer is faster
    return lo

Jebakan dan kasus tepi

Jumlah jam melampaui batas. Dengan kecepatan 1, 5000 tumpukan berisi 10^9 pisang membutuhkan 5 × 10^12 jam, melebihi batas 32-bit, dan total yang meluap dapat membuat kecepatan yang terlalu lambat lolos. Hitung dengan 64 bit, atau berhenti setelah total melebihi h.
Pembulatan ke bawah. 10 / 4 menghasilkan 2, tetapi tumpukan itu membutuhkan 3 jam.
Memulai rentang dari 0. Dengan begitu, mid bisa bernilai 0 dan jumlahnya akan dibagi dengan nol.
Mengatur hi = mid - 1 saat mid memenuhi syarat. Ini dapat membuang jawaban yang benar.
Memulai hi di bawah tumpukan terbesar. Saat h sama dengan jumlah tumpukan, setiap kecepatan yang lebih rendah tidak memenuhi syarat, dan pencarian mengembalikan salah satunya.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Koko Eating Bananas?

Pencarian biner berjalan dalam waktu O(n log m), dengan n sebagai jumlah tumpukan dan m sebagai tumpukan terbesar: sekitar log2(m) pemeriksaan, 30 saat m = 10^9, dan setiap pemeriksaan membaca semua tumpukan satu kali. Ruang tambahan yang digunakan adalah O(1).

Apa batas bawah dan batas atas untuk kecepatannya?

Batas atas adalah tumpukan terbesar: pada batas ini, setiap tumpukan membutuhkan satu jam, dan itu selalu cukup. Batas bawahnya adalah 1, dan kamu bisa menaikkannya menjadi jumlah total pisang dibagi h, dibulatkan ke atas, karena Koko makan paling banyak k pisang per jam.

Bagaimana cara membagi bilangan bulat dan membulatkan hasilnya ke atas?

Gunakan (p + k-1) / k dengan pembagian bilangan bulat. Menambahkan k-1 mendorong sisa apa pun melewati kelipatan k berikutnya, sedangkan kelipatan yang tepat tetap sama: 10 dengan kecepatan 4 menghasilkan 13 / 4 = 3, dan 8 menghasilkan 11 / 4 = 2. Tidak perlu menggunakan bilangan floating-point.

def minEatingSpeed(piles, h):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

piles = [4, 10, 7, 3]
h = 6

Output yang diharapkan