Koko Eating Bananas

Q: Koko Muz Yeme Problemi'nin zaman karmaşıklığı nedir?

İkili arama, O(n log m) zamanda çalışır; burada n yığın sayısı, m ise en büyük yığındır. Her kontrol her yığını bir kez okur ve hız aralığı her kontrolden sonra yarıya iner; bu nedenle yaklaşık log2(m) kontrol yapılır: m = 10^9 olduğunda 30. Ek alan kullanımı O(1) düzeyindedir.

Q: İkili arama yeme hızında neden işe yarar?

İkili arama, yanıtları sıralı olan bir evet-hayır sorusu gerektirir. “Koko k hızında bitirebilir mi?” böyle bir sorudur: Daha yüksek bir hız asla daha fazla saat gerektirmez; çünkü her yığındaki p / k değerinin yukarı yuvarlanmış hâli, k arttıkça yalnızca küçülebilir. Dolayısıyla yanıttan düşük her hız başarısız olur ve yanıta eşit ya da daha yüksek her hız başarılı olur; arama da sınırı bulur.

Q: Hızın alt ve üst sınırları nelerdir?

Üst sınır en büyük yığındır: bu hızda her yığın tam olarak bir saat sürer ve h yığın sayısından büyük ya da ona eşit olduğundan, her zaman yeterlidir. Daha yüksek bir hızda da her yığın için bir saat gerekir; dolayısıyla bunun üzerinde arama yapmak hiçbir şey kazandırmaz. Alt sınır 1'dir ve bunu, toplam muz sayısını h 'ye bölüp yukarı yuvarlayarak daraltabilirsiniz; çünkü Koko saatte en fazla k muz yer.

Q: Tamsayılarla nasıl bölme yapıp yukarı yuvarlayabilirsiniz?

Tamsayı bölmesiyle (p + k-1) / k kullanın. k-1 eklemek, kalanı bir sonraki k katının üzerine taşır ve tam kat olduğu durumda değer değişmez: hız 4 iken 10 için 13 / 4 = 3 , hız 4 iken 8 için 11 / 4 = 2 elde edilir. Büyük değerlerin yanlış yönde yuvarlanabildiği kayan noktalı aritmetiği kullanmaktan kaçınır.

Ortaİkili arama

+10

Koko'nun n muz yığını vardır; burada piles[i], i. yığındaki muz sayısını belirtir ve muhafızların geri dönmesine h saat vardır. Koko, saatte tam sayı olarak k muz yeme hızı seçer ve bu hızı korur. Her saat bir yığından k muz yer; o yığında k'den az muz kalmışsa yığını bitirir ve saat dolana kadar dinlenir. Tüm yığınları h saat içinde bitirmesini sağlayan en düşük k hızını döndürün.

Fonksiyon

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

pilesinteger-array: her yığındaki muz sayısı
hinteger: Koko'nun sahip olduğu saat sayısı
Döndürürinteger: h saat içinde her yığını bitiren, saatte muz cinsinden en küçük tam sayı yeme hızı

Kısıtlar

1 ≤ piles.length ≤ 5000
1 ≤ piles[i] ≤ 10⁹
piles.length ≤ h ≤ 10⁹, dolayısıyla her zaman bir yanıt vardır.

Örnekler

Girdi: piles = [4, 10, 7, 3]h = 6
Çıktı: 5
Açıklama: 5 hızında 4, 10, 7 ve 3 yığınları sırasıyla 1, 2, 2 ve 1 saat sürer: toplam 6 saat, bu da sığar. 4 hızında ise 1, 3, 2 ve 1 saat sürer; toplam 7 saat eder, yani 1 saat fazladır.

Gönderirken +22 gizli test

Ek soru

İkiz bir problem: Koko'nun d günü var ve verilen sırayla, günlük k muz sınırına sığdığı kadar tam yığını yiyor. En küçük k kaçtır ve ikili aramanın hangi iki kısmı değişir?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Buradaki yanıt, dizideki bir konum değil, bir hızdır; bu da ikili aramayı mümkün kılar. Bir hızı kontrol etmek, yığınlar üzerinde tek bir geçiş gerektirir. Kontroller ayrıca sıralı biçimde de ilerler: k hızı zamanında bitiriyorsa, daha hızlı olan tüm hızlar da bitirir. Böylece 1'den en büyük yığına kadar olan hızlar üzerinde ikili arama yapabilir ve yaklaşık 30 kontrol yapmanız yeterli olur; hızları teker teker denemek ise bir milyar kontrol gerektirebilir.

1'den başlayarak tüm hızları dene

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Tek bir soruyla başlayalım: p muzdan oluşan bir yığını k hızında yemek ne kadar sürer? Koko saatte k muz yer ve aynı saat içinde başka bir yığına geçmez; bu yüzden yığını yemek p / k saat sürer ve sonuç yukarı yuvarlanır. Hızı 4 olan 10 muzluk bir yığın 3 saat sürer: 4, 4, sonra 2 muz ve bir dinlenme. Bunu tüm yığınlar için toplayın ve toplamı h ile karşılaştırın.

Şimdi hızları sırayla deneyin: 1, 2, 3 ve böyle devam edin; toplamı h içine sığan ilk hızı döndürün. Daha yavaş her hız denenip başarısız olduğundan, tanım gereği bu en küçük hızdır. Döngü her zaman durur: en büyük yığının hızında her yığın bir saat sürer ve h, yığın sayısından en az büyüktür.

Sorun, döngünün ne kadar ilerleyebileceğidir. Neredeyse 10^9 muz içeren 5000 yığın ve h = 5000 olduğunda yanıt 10^9'a yakındır; bu yüzden döngü yaklaşık bir milyar kez çalışır ve her kontrolde 5000 yığının tümü okunur: yaklaşık 5 × 10^12 adım. Burada m, en büyük yığındır.

Algoritma

speed = 1 olarak ayarla.
Bu hızdaki saatleri say: her yığın için 64 bitlik bir toplam kullanarak (pile + speed-1) / speed değerini ekle.
Toplam h değerinden küçük veya eşitse speed değerini döndür.
Aksi takdirde speed değerini 1 artır ve yeniden say.

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

Hız üzerinde ikili arama

Sezgi

1'den en büyük yığına kadar her hızı, “bu hız süre içinde bitiriyor mu?” sorusuna verilen yanıtların bir satırı olarak düşün. Hız arttıkça her yığın için gereken saat sayısı aynı kalır veya azalır; dolayısıyla toplam süre yalnızca azalabilir. Bu nedenle satır, bir yerden itibaren hayır, hayır, hayır ve ardından evet şeklinde ilerler ve geri dönüş olmaz. İlk eveti arıyorsun; hayır ve evetlerden oluşan sıralı bir satır da ikili aramanın tam ortadan böldüğü şeydir.

Yanıtı her zaman içeren lo ile hi aralığını tut. Aralık 1 ve en büyük yığınla başlar; bu güvenlidir çünkü en büyük yığın hızında her yığın bir saat sürer ve h buna yeter. Ortadaki hız olan mid'i kontrol et. Süre yetiyorsa yanıt mid veya daha yavaş bir hızdır; bu yüzden hi = mid yap ve mid'i aralıkta tut. Süre yetmiyorsa daha yavaş tüm hızlar da başarısız olur; bu yüzden lo = mid + 1 yap. lo, hi'ye ulaştığında o hız yanıttır.

İlk örneği izle: yığınlar 4, 10, 7, 3 ve h = 6. Aralık 1 ile 10 arasındadır. 5 hızı 1 + 2 + 2 + 1 = 6 saat sürer; süre yeterlidir, bu yüzden aralık 1 ile 5 olur. 3 hızı 2 + 4 + 3 + 1 = 10 saat sürer; bu çok fazladır, bu yüzden aralık 4 ile 5 olur. 4 hızı 1 + 3 + 2 + 1 = 7 saat sürer; hâlâ çok fazladır, bu yüzden aralık 5 ile 5 olur ve yanıt 5'tir.

Her kontrol aralığı ikiye böler; bu nedenle en fazla 10^9 hız içeren bir aralık yaklaşık 30 kontrol gerektirir. Kontrol başına 5000 yığın için bu, trilyonlarca adım yerine yaklaşık 150000 adımdır.

Algoritma

lo = 1 olarak ayarla ve hi değerini en büyük yığın olarak belirle.
lo < hi olduğu sürece mid = lo + (hi - lo) / 2 değerini al.
mid hızındaki saatleri say: her yığın için 64 bitlik toplama (pile + mid-1) / mid ekle.
Toplam en fazla h ise hi = mid olarak ayarla; aksi hâlde lo = mid + 1 olarak ayarla.
Döngü sona erdiğinde lo değerini döndür.

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

Tuzaklar ve uç durumlar

Aramanın kendisi kısadır. Hatalar, saat hesabında ve aralığın sınırlarında gizlidir.

Saat sayısının taşması. Hız 1 iken, 10^9 muzdan oluşan 5000 yığın 5 × 10^12 saat sürer; bu, yaklaşık 2.1 × 10^9 olan 32 bitlik sınırın çok üzerindedir. Taşmış bir toplam küçük çıkabilir ve çok yavaş bir hızın denetimden geçmesine neden olabilir. 64 bitlik bir tamsayıyla sayın veya toplam h değerini geçer geçmez saymayı bırakın.
Yanlış yönde yuvarlama. Tamsayı bölmesi aşağı yuvarlar; bu nedenle 10 / 4 sonucu 2 olur, ancak bu yığın 3 saat sürer. (pile + k-1) / k ile yukarı yuvarlayın.
Aralığı 0'dan başlatmak. Böylece mid 0 olabilir ve saat hesabındaki bölme sıfıra bölme hatasına yol açar. Gerçek en düşük hız 1'dir.
mid uygun olduğunda hi değerini mid - 1 yapmak. Bu, yanıtın kendisini aralıktan çıkarabilir. Çalışan ilk hızı ararken, hi = mid ile mid değerini aralıkta tutun ve lo < hi koşuluyla döngü kurun.
hi değerini en büyük yığından küçük başlatmak. h yığın sayısına eşit olduğunda, bunun altındaki tüm hızlar başarısız olabilir; bu nedenle arama çalışmayan bir hız döndürür.

Sıkça sorulan sorular4

Koko Muz Yeme Problemi'nin zaman karmaşıklığı nedir?

İkili arama, O(n log m) zamanda çalışır; burada n yığın sayısı, m ise en büyük yığındır. Her kontrol her yığını bir kez okur ve hız aralığı her kontrolden sonra yarıya iner; bu nedenle yaklaşık log2(m) kontrol yapılır: m = 10^9 olduğunda 30. Ek alan kullanımı O(1) düzeyindedir.

İkili arama yeme hızında neden işe yarar?

İkili arama, yanıtları sıralı olan bir evet-hayır sorusu gerektirir. “Koko k hızında bitirebilir mi?” böyle bir sorudur: Daha yüksek bir hız asla daha fazla saat gerektirmez; çünkü her yığındaki p / k değerinin yukarı yuvarlanmış hâli, k arttıkça yalnızca küçülebilir. Dolayısıyla yanıttan düşük her hız başarısız olur ve yanıta eşit ya da daha yüksek her hız başarılı olur; arama da sınırı bulur.

Hızın alt ve üst sınırları nelerdir?

Üst sınır en büyük yığındır: bu hızda her yığın tam olarak bir saat sürer ve h yığın sayısından büyük ya da ona eşit olduğundan, her zaman yeterlidir. Daha yüksek bir hızda da her yığın için bir saat gerekir; dolayısıyla bunun üzerinde arama yapmak hiçbir şey kazandırmaz. Alt sınır 1'dir ve bunu, toplam muz sayısını h'ye bölüp yukarı yuvarlayarak daraltabilirsiniz; çünkü Koko saatte en fazla k muz yer.

Tamsayılarla nasıl bölme yapıp yukarı yuvarlayabilirsiniz?

Tamsayı bölmesiyle (p + k-1) / k kullanın. k-1 eklemek, kalanı bir sonraki k katının üzerine taşır ve tam kat olduğu durumda değer değişmez: hız 4 iken 10 için 13 / 4 = 3, hız 4 iken 8 için 11 / 4 = 2 elde edilir. Büyük değerlerin yanlış yönde yuvarlanabildiği kayan noktalı aritmetiği kullanmaktan kaçınır.

Python

def minEatingSpeed(piles, h):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

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

Beklenen