Book Allocation Problem
על מדף מונחים ספרים בסדר קבוע, ו־pages[i] הוא מספר העמודים בספר i. חלקו את הספרים בין students תלמידים: כל תלמיד יקבל רצף אחד רציף של ספרים סמוכים, לפחות ספר אחד לכל תלמיד, וכל ספר יינתן לתלמיד אחד בדיוק. העומס של תלמיד הוא המספר הכולל של העמודים שהוא מקבל.
החזירו את הערך הקטן ביותר האפשרי של העומס הכבד ביותר. אם יש יותר תלמידים מספרים, החזירו -1.
פונקציה
- pagesinteger-array
- מספר העמודים של כל ספר, לפי הסדר על המדף
- studentsinteger
- מספר התלמידים שחולקים את הספרים
- מחזירהinteger
- העומס המרבי המינימלי האפשרי, או -1 כשיש יותר תלמידים מספרים
אילוצים
1 ≤ pages.length ≤ 50001 ≤ pages[i] ≤ 1051 ≤ students ≤ 104- החזר
-1כאשרstudents > pages.length.
דוגמאות
- קלט
- pages = [25, 40, 15, 30, 50]students = 3
- פלט
- 65
- הסבר
- חלק את
[25, 40], את[15, 30]ואת[50]: העומסים הם 65, 45 ו־50. מגבלה של 64 נכשלת: החלוקה נותנת[25],[40, 15],[30],[50]— ארבעה תלמידים.
- קלט
- pages = [10, 20]students = 3
- פלט
- -1
- הסבר
- אי אפשר לתת לשלושה תלמידים ספר אחד לכל אחד מתוך שני ספרים, לכן התשובה היא
-1.
- קלט
- pages = [7, 3, 9]students = 3
- פלט
- 9
- הסבר
- שלושה ספרים ושלושה תלמידים, וכל תלמיד מקבל ספר אחד. הספר הכבד ביותר הוא הספר בן 9 העמודים.
שאלת המשך
הוכיחו שהממוצע של מספר הספרים בחלוקה בין המדפים, בעיגול כלפי מעלה, בתוספת הספר העבה ביותר, הוא תמיד גבול שעובד. כמה בדיקות חוסך הגבול העליון הזה במדף של ספרים דקים?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
במקום לחפש את החיתוכים הטובים ביותר, בחר מגבלת עמודים. כמה תלמידים דרושים לך אם אסור לאף אחד לשאת יותר מהמגבלה הזאת?
חלק ספרים לפי הסדר שעל המדף ועבור לתלמיד הבא רק כאשר הספר הבא יחרוג מהמגבלה. מגבלה גבוהה יותר לעולם אינה דורשת יותר תלמידים.
החזר
-1כשיש יותר תלמידים מספרים. אחרת, בצע חיפוש בינארי אחר המגבלה, מהגדול מבין הספר העבה ביותר והחלק הממוצע ועד לסכום הכולל.
פתרון
יש יותר מדי דרכים לחתוך את המדף, אבל זול לבדוק מגבלת עמודים אחת: מחלקים ספרים לפי הסדר שעל המדף, עוברים לתלמיד הבא כשספר היה חורג מהמגבלה, וסופרים את התלמידים. מגבלה גבוהה יותר אף פעם לא דורשת יותר תלמידים, לכן המגבלות שעובדות יוצרות רצף אחד, וחיפוש בינארי מוצא היכן הוא מתחיל.
העלה את מגבלת העמוד בעמוד אחד בכל פעם
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
מתחילים ב־L = max(pages), כי מישהו נושא את הספר העבה ביותר, ומגדילים את L בעמוד אחד בכל פעם עד שהספירה החמדנית נכנסת במסגרת מספר ה־students. כל גבול נמוך יותר נכשל, ולכן הגבול הראשון שמתאים הוא התשובה. בדוגמה הראשונה כל גבול מ־50 עד 64 דורש ארבעה תלמידים, ו־65 דורש שלושה: 16 בדיקות.
התשובה יכולה להיות המדף כולו: תלמיד אחד ו־5000 ספרים בני 10^5 עמודים פירושם בערך 5 × 10^8 גבולות, כשכל אחד מהם דורש מעבר על 5000 ספרים. בעמודת הזמן, A הוא התשובה ו־m הוא הספר העבה ביותר.
אלגוריתם
- אם
students > pages.length, החזר-1. - כתוב את הספירה החמדנית עבור מגבלה
L: התחל עם תלמיד אחד ועומס של 0; כאשרload + pages[i] > L, הוסף תלמיד והגדר את העומס ל-pages[i], אחרת הוסף את הספר לעומס. - הגדר את
Lלספר העבה ביותר. - כל עוד הספירה עבור
Lגדולה מ-students, הוסף 1 ל-L. - החזר את
L.
def studentsNeeded(pages, limit):
count, load = 1, 0 # the first student starts with no pages
for p in pages:
if load + p > limit:
count += 1 # this book opens the next student's block
load = p
else:
load += p
return count
def allocateBooks(pages, students):
if students > len(pages):
return -1 # someone would get no book
limit = max(pages) # the thickest book has to fit somewhere
while studentsNeeded(pages, limit) > students:
limit += 1
return limitחיפוש בינארי במגבלת העמוד
האינטואיציה
המספר החמדני הוא מספר התלמידים הקטן ביותר שנדרש בכל חלוקה תחת L. בהשוואה תלמיד מול תלמיד לכל חלוקה אחרת, כל תלמיד בחלוקה החמדנית עוצר רק כשהספר הבא אינו מתאים, ולכן הוא מסיים לפחות באותה נקודה על המדף. זה בסדר שיהיו פחות תלמידים ממה שיש לך: תלמיד שמחזיק שני ספרים יכול להעביר אחד לתלמיד שאין לו ספרים, ושום עומס אינו גדל.
לכן L מתאים בדיוק כשהמספר החמדני קטן או שווה ל-students. כל מה שמתאים תחת L מתאים גם תחת L+1, ולכן חיפוש בינארי מוצא את הגבול הראשון שמתאים.
טווח החיפוש מתחיל בערך הגדול מבין max(pages) והממוצע לחלוקה, total / students בעיגול כלפי מעלה, מכיוון שהעומס הכבד ביותר הוא לפחות כמו שניהם. הגבול העליון הוא total. בדוגמה הראשונה מדובר ב-54 עד 160, והחיפוש מנסה את 107, 80, 67, 60, 64, 66 ו-65.
אלגוריתם
- אם
students > pages.length, החזר-1. - סכום את
totalומצא את הספר העבה ביותר. הגדר אתloלערך הגדול יותר מבין הספר העבה ביותר ובין(total + students - 1) / students, ואתhi = total. - כל עוד
lo < hi, קבע אתmid = lo + (hi - lo) / 2. - הרץ את ספירת החמדנית עבור
mid. אם התוצאה לכל היותרstudents, הגדר אתhi = mid; אחרת הגדר אתlo = mid + 1. - החזר את
lo.
def studentsNeeded(pages, limit):
count, load = 1, 0 # the first student starts with no pages
for p in pages:
if load + p > limit:
count += 1 # this book opens the next student's block
load = p
else:
load += p
return count
def allocateBooks(pages, students):
if students > len(pages):
return -1 # someone would get no book
total = sum(pages)
# no limit can be below the thickest book or below the average share
lo = max(max(pages), (total + students - 1) // students)
hi = total # one student could carry the whole shelf
while lo < hi:
mid = lo + (hi - lo) // 2
if studentsNeeded(pages, mid) <= students:
hi = mid # mid is enough, so the answer is mid or lower
else:
lo = mid + 1 # mid needs too many students
return lo
מלכודות ומקרי קצה
- דילוג על הבדיקה של
-1. עבור[10, 20]ו-3 תלמידים, הספירה החמדנית בגבול של 20 היא 2, ולכן החיפוש מחזיר 20. - התחלת הטווח בממוצע של החלק בלבד. עבור
[1, 9]ו-2 תלמידים, הממוצע הוא 5, ובגבול הזה האלגוריתם החמדני מקצה את הספר בן 9 העמודים לבדו, סופר 2 ומחזיר 5. - בדיקה אם התוצאה היא בדיוק
students. עבור[5, 5, 5, 5, 5, 5]ו-4 תלמידים, התשובה היא 10, ובו הספירה החמדנית היא 3. - מיון הספרים. עבור
[10, 1, 1, 10]עם 2 תלמידים, התוצאה היא 11, אבל לאחר מיון ל-[1, 1, 10, 10]התוצאה היא 12.
שאלות נפוצות3
האם בעיית הקצאת הספרים זהה לבעיית פיצול המערך כך שהסכום הגדול ביותר יהיה מינימלי?
כן. שניהם מחלקים מערך למספר קבוע של בלוקים רציפים שאינם ריקים וממזערים את סכום הבלוק הגדול ביותר, ואותה חיפוש בינארי עם אותה בדיקה חמדנית פותרת את שניהם. בגרסת הספר נוסף המקרה של -1.
מהי סיבוכיות הזמן של בעיית הקצאת הספרים?
זמן O(n log S) ומקום נוסף O(1), כאשר n הוא מספר הספרים ו-S הוא מספר העמודים הכולל. כל מגבלה שנבדקת דורשת מעבר אחד על הספרים, והחיפוש בודק בערך log2 S מגבלות: 29 במדף עם 5 × 10^8 עמודים.
מתי אי אפשר להקצות את הספרים?
רק כאשר מספר התלמידים גדול ממספר הספרים, מכיוון שכל תלמיד זקוק לספר אחד לפחות. כשיש מספיק ספרים, כל גוש של שני ספרים או יותר יכול לתת את הספר האחרון שלו לתלמיד שאין לו ספר, עד שלכולם יהיה ספר אחד.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def allocateBooks(pages, students):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנטים
pages = [25, 40, 15, 30, 50] students = 3
הפלט הצפוי
65