Koko Eating Bananas
Koko'nun n muz yığını vardır; i. yığında piles[i] muz bulunur ve h saati vardır. Saatte k muzluk bir yeme hızı seçer; k tam sayı olmalıdır ve seçtiği hızı değiştirmez. Her saat bir yığından k muz yer; o yığında k'den az muz kaldıysa yığını bitirir ve saat dolana kadar dinlenir. Tüm yığınları h saat içinde bitirmesini sağlayan en küçük k değerini döndürün.
Fonksiyon
- pilesinteger-array
- her yığındaki muz sayısı
- hinteger
- Koko'nun sahip olduğu saat sayısı
- Döndürürinteger
- saatte muz cinsinden, her yığını h saat içinde bitiren en düşük tam sayı yeme hızı
Kısıtlar
1 ≤ piles.length ≤ 50001 ≤ piles[i] ≤ 109piles.length ≤ h ≤ 109, dolayısıyla her zaman bir cevap vardır.
Örnekler
- Girdi
- piles = [4, 10, 7, 3]h = 6
- Çıktı
- 5
- Açıklama
- Hız 5'te 4, 10, 7 ve 3 yığınları sırasıyla 1, 2, 2 ve 1 saat alır: toplam 6 saat, bu da sığar. Hız 4'te ise sırasıyla 1, 3, 2 ve 1 saat alırlar; bu da 7 saat eder.
- Girdi
- piles = [30, 11, 23, 4, 20]h = 5
- Çıktı
- 30
- Açıklama
- Beş yığın ve beş saat, yığın başına tam olarak bir saat bırakır; bu nedenle hız, en büyük yığın olan 30'u bir saatte bitirmelidir. Hız 29 olursa, bu yığın için ikinci bir saat gerekir.
- Girdi
- piles = [5, 9, 2]h = 20
- Çıktı
- 1
- Açıklama
- 1 hızında yığınlar 5 + 9 + 2 = 16 saat sürer; bu, 20 saatlik sürenin oldukça altındadır. 1'den daha yavaş bir hız olmadığından cevap 1'dir.
Ek soru
Twin problem: Koko, d gün içinde, günde en fazla k muz yiyerek bütün yığınları sırayla bitiriyor. En küçük k değeri nedir ve aramanızda ne değişir?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Bir
khızı belirleyin. Koko’nun bir saat içinde yığın değiştirmediğini göz önünde bulundurarak, bu hızdapmuzdan oluşan bir yığının bitmesi kaç saat sürer? Tüm yığınların bitmesi kaç saat sürer?khızı süre içinde bitiriyorsa, daha hızlı olan her hız da bitirir. İşe yarayan hızlar, yanıtla başlayan kesintisiz bir aralık oluşturur.1'den en büyük yığına kadar olan hızlar üzerinde ikili arama yapın. Orta hızdaki saat sayısını tek geçişte hesaplayın: eğer
hsaat içine sığıyorsa, yanıt en fazla orta hızdır; aksi hâlde orta hızdan büyüktür.
Çözüm
Yanıt, dizideki bir konum değil, bir hızdır ve bu durum ikili aramayı gizler. Bir hızı kontrol etmek, yığınların üzerinden bir kez geçmeyi gerektirir ve k hızı süre içinde bitiriyorsa, daha hızlı olan tüm hızlar da bitirir. Bu yüzden hızlar üzerinde 1'den en büyük yığına kadar ikili arama yapın: bir milyara kadar kontrol yerine yaklaşık 30 kontrol.
1'den başlayarak tüm hızları deneyin
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Koko bir saat içinde başka bir yığına geçmez; bu nedenle p muzluk bir yığını bitirmesi, yukarı yuvarlandığında p / k saat sürer: 4 hızında 10 muz 3 saat sürer. 1, 2, 3 ve böyle devam eden hızları deneyin ve toplam süresi h değerini aşmayan ilk hızı döndürün. Bu hız en küçüğüdür; çünkü daha yavaş tüm hızlar başarısız olmuştur. Döngü, her yığının bir saat sürdüğü en büyük yığının hızında sona erer.
m en büyük yığın olduğunda, bu n yığın için en fazla m kontrol demektir: 10^9 civarındaki 5000 yığın ve h = 5000 için yaklaşık 5 × 10^12 adım.
Algoritma
speed = 1olarak ayarla.- Bu hızdaki saatleri say: her yığın için 64 bitlik bir toplam kullanarak
(pile + speed-1) / speedekle. - Toplam
hdeğerinden küçük veya ona eşitsespeeddeğerini döndür. - Aksi takdirde
speeddeğ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 += 1Hız üzerinde ikili arama
Sezgi
Hız arttıkça her yığının bitmesi için gereken saat sayısı aynı kalır veya azalır; bu yüzden “bu hız zamanında bitirir mi?” sorusunun yanıtları, cevaptan itibaren evet olacak şekilde, hayır, hayır, hayır, sonra evet biçimindedir. İkili arama ilk eveti bulur.
Yanıtı her zaman içeren lo ile hi arasında bir aralık tut; bu aralık 1 ve en büyük yığınla başlar. En büyük yığının hızı, yığın başına bir saat sürdüğü için süreye sığar. Orta hız mid süreye sığıyorsa, yanıt mid veya daha yavaşıdır; bu yüzden hi = mid olarak ayarla. Sığmıyorsa, daha yavaş tüm hızlar da başarısız olur; bu yüzden lo = mid + 1 olarak ayarla. lo ile hi eşitlendiğinde yanıt bulunmuş olur.
İlk örnekte aralık 1 ile 10 arasında başlar. 5 hızı süreye sığar, dolayısıyla aralık 1 ile 5 olur; 3 hızı 10 saat sürer, dolayısıyla aralık 4 ile 5 olur; 4 hızı 7 saat sürer, dolayısıyla aralık 5 ile 5 olur.
Algoritma
lo = 1olarak ayarla vehideğerini en büyük yığın olarak belirle.lo < hiolduğu sürecemid = lo + (hi - lo) / 2değerini al.midhızında gereken saatleri hesapla: her yığın için(pile + mid-1) / middeğerini 64 bitlik bir toplama ekle.- Toplam
hdeğerinden küçük veya ona eşitsehi = midolarak ayarla; değilselo = mid + 1olarak ayarla. lodeğ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
- Saat sayısının taşması. Hız 1 iken,
10^9muzdan oluşan 5000 yığın5 × 10^12saat sürer; bu, 32 bitlik sınırı aşar ve taşmış bir toplam, yavaş bir hızın geçerli sayılmasına yol açabilir. 64 bit kullanarak sayın veya toplamhdeğerini geçince durun. - Aşağı yuvarlama.
10 / 4sonucu 2’dir, ancak bu yığın 3 saat sürer. - Aralığı 0’dan başlatmak. Böylece
mid0 olabilir ve sayma işlemi sıfıra bölmeye yol açar. miduygun olduğundahi = mid - 1atamak. Bu, yanıtı arama aralığının dışında bırakabilir.hideğerini en büyük yığından küçük başlatmak.hyığın sayısına eşitse, daha düşük tüm hızlar başarısız olur ve arama bunlardan birini döndürür.
Sıkça sorulan sorular3
Koko Eating Bananas'ın 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: yaklaşık log2(m) kontrol, m = 10^9 olduğunda 30 kontrol yapılır ve her kontrolde her yığın bir kez okunur. Ek alan kullanımı O(1)'dir.
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 bir saat sürer ve bu süre her zaman yeterlidir. Alt sınır 1'dir; bunu, Koko saatte en fazla k muz yediği için toplam muz sayısının h'ye bölünüp yukarı yuvarlanmış değerine yükseltebilirsin.
Tamsayılarla nasıl bölme yapar ve yukarı yuvarlarsınız?
Tamsayı bölmesiyle (p + k-1) / k kullanın. k-1 eklemek, kalan değeri k’nin bir sonraki katının ötesine taşır ve tam katlar aynı kalır: 4 hızında 10, 13 / 4 = 3 sonucunu verir; 8 ise 11 / 4 = 2 sonucunu verir. Kayan noktalı sayılara gerek yoktur.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def minEatingSpeed(piles, h):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argümanlar
piles = [4, 10, 7, 3] h = 6
Beklenen Çıktı
5