Koko Eating Bananas

Q: מהי סיבוכיות הזמן של אכילת בננות על ידי Koko?

החיפוש הבינארי פועל בזמן O(n log m) , כאשר n הוא מספר הערימות ו- m היא הערימה הגדולה ביותר: בערך log2(m) בדיקות, 30 כאשר m = 10^9 , וכל אחת מהן קוראת כל ערימה פעם אחת. הזיכרון הנוסף הוא O(1) .

Q: מהם הגבולות התחתון והעליון של המהירות?

הגבול העליון הוא הערימה הגדולה ביותר: בקצב הזה כל ערימה אורכת שעה אחת, וזה תמיד מספיק. הגבול התחתון הוא 1, ואפשר להעלות אותו למספר הכולל של הבננות חלקי h , בעיגול כלפי מעלה, כי קוקו אוכלת לכל היותר k בננות בשעה.

Q: איך מחלקים ומעגלים כלפי מעלה עם מספרים שלמים?

השתמשו ב־ (p + k-1) / k עם חלוקה של מספרים שלמים. הוספת k-1 דוחפת כל שארית אל מעבר לכפולה הבאה של k , וכפולה מדויקת נשארת במקומה: במהירות 4, הערך 10 נותן 13 / 4 = 3 , ו־8 נותן 11 / 4 = 2 . אין צורך במספרים נקודה צפה.

בינוניחיפוש בינארי

+10

לקוקו יש n ערמות בננות, כאשר בערמה i יש piles[i] בננות, ונותרו לה h שעות. היא בוחרת מהירות אכילה k, מספר שלם של בננות לשעה, ומתמידה בה. בכל שעה היא אוכלת k בננות מערמה אחת; אם נותרו בערמה הזו פחות מ־k בננות, היא מסיימת אותה ונחה עד סוף השעה. החזירו את ערך ה־k הקטן ביותר שיאפשר לה לסיים את כל הערמות בתוך h שעות.

פונקציה

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

pilesinteger-array: מספר הבננות בכל ערימה
hinteger: מספר השעות שיש לקוקו
מחזירהinteger: מהירות האכילה השלמה הקטנה ביותר, בבננות לשעה, שמספיקה לסיים כל ערימה בתוך h שעות

אילוצים

1 ≤ piles.length ≤ 5000
1 ≤ piles[i] ≤ 10⁹
piles.length ≤ h ≤ 10⁹, לכן תמיד קיימת תשובה.

דוגמאות

קלט: piles = [4, 10, 7, 3]h = 6
פלט: 5
הסבר: במהירות 5 הערימות 4, 10, 7 ו-3 דורשות 1, 2, 2 ו-1 שעות: 6 בסך הכול, וזה מתאים. במהירות 4 הן דורשות 1, 3, 2 ו-1, כלומר 7.

שאלת המשך

בעיית התאומים: קוקו אוכלת ערמות שלמות לפי הסדר, עד k בננות ביום, בתוך d ימים. מהו k הקטן ביותר, ומה משתנה בחיפוש שלך?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

התשובה היא מהירות, לא מיקום במערך, וזה מאפשר להשתמש בחיפוש בינארי. בדיקת מהירות אחת דורשת מעבר אחד על הערימות, ואם מהירות k מספיקה לסיים בזמן, כל מהירות גבוהה יותר תספיק גם היא. לכן מבצעים חיפוש בינארי במהירויות מ־1 ועד לערימה הגדולה ביותר: כ־30 בדיקות במקום עד מיליארד.

נסו כל מהירות החל מ־1 ומעלה

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

קוקו לעולם לא עוברת לערימה אחרת במהלך שעה, לכן אכילת ערימה של p בננות אורכת p / k שעות, בעיגול כלפי מעלה: במהירות 4, אכילת 10 בננות אורכת 3 שעות. נסו מהירויות 1, 2, 3 וכן הלאה, והחזירו את המהירות הראשונה שבה הזמן הכולל לא עולה על h. זו המהירות הקטנה ביותר, כי כל מהירות נמוכה יותר נכשלה, והלולאה נעצרת במהירות של הערימה הגדולה ביותר, שבה אכילת כל ערימה אורכת שעה אחת.

אם m היא הערימה הגדולה ביותר, יש עד m בדיקות של n ערימות: כ־5 × 10^12 צעדים עבור 5000 ערימות שגודלן קרוב ל־10^9 ו־h = 5000.

אלגוריתם

הגדירו speed = 1.
ספרו את השעות במהירות הזו: עבור כל ערימה הוסיפו (pile + speed-1) / speed, תוך שימוש בסכום של 64 סיביות.
אם הסכום הוא לכל היותר h, החזירו את speed.
אחרת הוסיפו 1 ל-speed וספרו שוב.

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

חיפוש בינארי לפי מהירות

האינטואיציה

ככל שהמהירות גדלה, כל ערימה דורשת אותו מספר שעות או פחות, ולכן התשובות לשאלה "האם המהירות הזאת מספיקה כדי לסיים בזמן?" הן לא, לא, לא, ואז כן, החל מהתשובה ואילך. חיפוש בינארי מוצא את הכן הראשון הזה.

שומרים על טווח מ־lo עד hi שתמיד כולל את התשובה, ומתחילים ב־1 ובערימה הגדולה ביותר, שהמהירות שלה דורשת שעה לכל ערימה ולכן עומדת במגבלת הזמן. אם המהירות האמצעית mid מספיקה, התשובה היא mid או איטית יותר, ולכן מגדירים hi = mid. אם לא, כל מהירות איטית יותר גם נכשלת, ולכן מגדירים lo = mid + 1. כש־lo מגיע ל־hi, זו התשובה.

בדוגמה הראשונה הטווח מתחיל מ־1 עד 10. מהירות 5 מספיקה, ולכן הטווח הופך ל־1 עד 5; במהירות 3 נדרשות 10 שעות, ולכן הטווח הוא 4 עד 5; במהירות 4 נדרשות 7 שעות, ולכן הטווח הוא 5 עד 5.

אלגוריתם

מגדירים את lo = 1 ואת hi לערימה הגדולה ביותר.
כל עוד lo < hi, מחשבים mid = lo + (hi - lo) / 2.
סופרים את השעות במהירות mid: מוסיפים (pile + mid-1) / mid עבור כל ערימה, לסכום כולל של 64 סיביות.
אם הסכום הכולל קטן או שווה ל-h, מגדירים hi = mid; אחרת מגדירים lo = mid + 1.
מחזירים את 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

מלכודות ומקרי קצה

חריגה בספירת השעות. במהירות 1, נדרשות 5000 ערימות של 10^9 בננות 5 × 10^12 שעות, יותר ממגבלת 32 הסיביות, וסכום שגלש יכול לגרום למהירות איטית לעבור. יש לספור ב-64 סיביות, או לעצור ברגע שהסכום עובר את h.
עיגול כלפי מטה. 10 / 4 נותן 2, אבל נדרשות 3 שעות לטיפול בערימה הזאת.
התחלת הטווח ב-0. אז mid יכול להיות 0, והספירה תחלק באפס.
הגדרת hi = mid - 1 כאשר mid מתאים. כך עלולים לדלג על התשובה.
התחלת hi מתחת לערימה הגדולה ביותר. כאשר h שווה למספר הערימות, כל מהירות נמוכה יותר נכשלת, והחיפוש מחזיר אחת מהן.

שאלות נפוצות3

מהי סיבוכיות הזמן של אכילת בננות על ידי Koko?

החיפוש הבינארי פועל בזמן O(n log m), כאשר n הוא מספר הערימות ו-m היא הערימה הגדולה ביותר: בערך log2(m) בדיקות, 30 כאשר m = 10^9, וכל אחת מהן קוראת כל ערימה פעם אחת. הזיכרון הנוסף הוא O(1).

מהם הגבולות התחתון והעליון של המהירות?

הגבול העליון הוא הערימה הגדולה ביותר: בקצב הזה כל ערימה אורכת שעה אחת, וזה תמיד מספיק. הגבול התחתון הוא 1, ואפשר להעלות אותו למספר הכולל של הבננות חלקי h, בעיגול כלפי מעלה, כי קוקו אוכלת לכל היותר k בננות בשעה.

איך מחלקים ומעגלים כלפי מעלה עם מספרים שלמים?

השתמשו ב־(p + k-1) / k עם חלוקה של מספרים שלמים. הוספת k-1 דוחפת כל שארית אל מעבר לכפולה הבאה של k, וכפולה מדויקת נשארת במקומה: במהירות 4, הערך 10 נותן 13 / 4 = 3, ו־8 נותן 11 / 4 = 2. אין צורך במספרים נקודה צפה.

def minEatingSpeed(piles, h):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

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

הפלט הצפוי