Koko Eating Bananas

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

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

Q: למה חיפוש בינארי עובד על מהירות האכילה?

חיפוש בינארי זקוק לשאלה שהתשובה עליה היא כן או לא, ושאפשר למיין את תשובותיה. „האם קוקו יכולה לסיים במהירות k?” היא שאלה כזאת: במהירות גבוהה יותר אף פעם לא נדרשות יותר שעות, כי העיגול כלפי מעלה של p / k עבור כל ערימה יכול רק לקטון ככל ש- k גדל. לכן כל מהירות שמתחת לתשובה נכשלת, וכל מהירות מהתשובה ומעלה מצליחה, והחיפוש מוצא את הגבול.

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

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

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

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

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

+10

לקוקו יש n ערימות של בננות, כאשר piles[i] הוא מספר הבננות בערימה 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, שעה אחת יותר מדי.

+22 בדיקות נסתרות בשליחה

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

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

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

האינטואיציה

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

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

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

אלגוריתם

הגדר את 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

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

האינטואיציה

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

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

עקבו אחר הדוגמה הראשונה: ערימות 4, 10, 7, 3, עם h = 6. הטווח הוא מ־1 עד 10. במהירות 5 נדרשות 1 + 2 + 2 + 1 = 6 שעות, וזה מתאים, ולכן הטווח הופך ל־1 עד 5. במהירות 3 נדרשות 2 + 4 + 3 + 1 = 10 שעות, יותר מדי, ולכן הטווח הופך ל־4 עד 5. במהירות 4 נדרשות 1 + 3 + 2 + 1 = 7 שעות, עדיין יותר מדי, ולכן הטווח הופך ל־5 עד 5, והתשובה היא 5.

כל בדיקה חוצה את הטווח לשניים, ולכן טווח של עד 10^9 מהירויות דורש כ־30 בדיקות. ב־5000 ערימות לבדיקה, מדובר בכ־150000 צעדים במקום טריליונים.

אלגוריתם

הגדירו את 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 סיביות, שעומד על כ־2.1 × 10^9. סכום שגולש עלול לצאת קטן ולאפשר למהירות איטית מדי לעבור את הבדיקה. ספרו באמצעות מספר שלם של 64 סיביות, או הפסיקו לספור ברגע שהסכום עובר את h.
עיגול בכיוון הלא נכון. חלוקה של מספרים שלמים מעגלת כלפי מטה, לכן 10 / 4 נותן 2, אבל הערימה הזאת דורשת 3 שעות. עגלו כלפי מעלה באמצעות (pile + k-1) / k.
התחלת הטווח ב־0. אז mid יכול להיות 0, ומספר השעות יתחלק באפס. המהירות האיטית ביותר האפשרית היא 1.
העברת hi ל־mid - 1 כאשר mid מתאים. כך אפשר להשליך את התשובה עצמה. כשמחפשים את המהירות הראשונה שעובדת, השאירו את mid בטווח באמצעות hi = mid והמשיכו בלולאה כל עוד lo < hi.
התחלת hi מתחת לערימה הגדולה ביותר. מהירויות שמתחתיה עלולות כולן להיכשל כאשר h שווה למספר הערימות, ולכן החיפוש יחזיר מהירות שאינה עובדת.

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

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

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

למה חיפוש בינארי עובד על מהירות האכילה?

חיפוש בינארי זקוק לשאלה שהתשובה עליה היא כן או לא, ושאפשר למיין את תשובותיה. „האם קוקו יכולה לסיים במהירות k?” היא שאלה כזאת: במהירות גבוהה יותר אף פעם לא נדרשות יותר שעות, כי העיגול כלפי מעלה של p / k עבור כל ערימה יכול רק לקטון ככל ש-k גדל. לכן כל מהירות שמתחת לתשובה נכשלת, וכל מהירות מהתשובה ומעלה מצליחה, והחיפוש מוצא את הגבול.

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

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

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

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

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

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

צפוי