Minimum Cost of Ropes
יש לך כמה חבלים, ו-ropes[i] הוא האורך של חבל i. אפשר לחבר כל שני חבלים לחבל אחד שאורכו סכום האורכים שלהם, ועלות החיבור היא אותו הסכום. ממשיכים לחבר עד שנותר חבל אחד.
כתבו פונקציה בשם minCostRopes שמחזירה את העלות הכוללת הקטנה ביותר של חיבור כל החבלים לחבל אחד, או 0 אם מלכתחילה יש רק חבל אחד.
פונקציה
- ropesinteger-array
- האורך של כל חבל
- מחזירהinteger
- העלות הכוללת הקטנה ביותר של חיבור כל החבלים לחבל אחד
אילוצים
1 ≤ ropes.length ≤ 1041 ≤ ropes[i] ≤ 100- התשובה נכנסת למספר שלם עם סימן בן 32 סיביות.
דוגמאות
- קלט
- ropes = [5, 2, 8, 3]
- פלט
- 33
- הסבר
- חברו את
2ואת3לקבלת 5, את שני החבלים שאורכם5לקבלת 10, ואז את8ואת10לקבלת 18. הסכום הכולל הוא 5 + 10 + 18 = 33.
- קלט
- ropes = [7]
- פלט
- 0
- הסבר
- יש רק חבל אחד, ולכן לא מתבצע חיבור ולא משלמים דבר.
- קלט
- ropes = [1, 1, 1, 1]
- פלט
- 8
- הסבר
- חבר את ה־
1ים בזוגות, בעלות של 2 לכל זוג, ואז חבר את שני החבלים באורך2בעלות של 4: בסך הכול 8. הוספת כל1לחבל אחד שהולך ומתארך הייתה עולה 2 + 3 + 4 = 9.
שאלת המשך
נניח שחיבור יכול לקשור עד שלושה חבלים ועלותו היא כאורך הכולל שלהם. איך משתנה הכלל הגרידי כאשר מספר החבלים אינו מתחלק באופן שווה?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
כתבו את העלות הכוללת כסכום על פני החבלים המקוריים. כמה פעמים משלמים על האורך של חבל אחד?
משלמים פעם אחת על אורכו של חבל עבור כל חיבור שהוא משתתף בו, לכן החבלים הארוכים ביותר צריכים להשתתף בכמה שפחות חיבורים. חיבור שני החבלים הקצרים ביותר שיש לך הוא תמיד צעד ראשון בטוח.
הכניסו כל חבל לערימת מינימום. שלפו את שני החבלים הקצרים ביותר, הוסיפו את הסכום שלהם לעלות, החזירו את הסכום לערימה וחזרו על הפעולה עד שנשאר חבל אחד.
פתרון
כל חיבור עולה באורך המלא של שני החלקים, ולכן על חיבור של חבל מוקדם משלמים שוב בכל חיבור מאוחר יותר שהוא משתתף בו. השאירו את החבלים הארוכים מחוץ לחיבורים המוקדמים: חברו את שני החבלים הקצרים ביותר בכל סבב. ערימת מינימום מוצאת את שני אלה ב־O(log n).
סרוק בכל סבב כדי למצוא את שני הקצרים ביותר
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
בכל סבב סרקו את הערימה, מצאו את החבל הקצר ביותר והוציאו אותו, סרקו שוב כדי למצוא את החבל הקצר הבא, והחזירו את החבל שחיברתם.
למה דווקא שני החבלים הקצרים ביותר: ציירו את החיבורים כעץ, כשהחבלים הם העלים. משלמים את אורכו של חבל פעם אחת על כל חיבור שמעליו, כלומר לפי העומק שלו. ברמה העמוקה ביותר יש שני עלים צמודים, והעברת שני החבלים הקצרים ביותר לשם לעולם אינה מגדילה את העלות. לכן, קיימת תוכנית זולה ביותר שמחברת תחילה את שני החבלים הקצרים ביותר, והטיעון חוזר על עצמו בערימה הקטנה יותר.
יש n-1 סבבים של שתי סריקות מלאות: O(n²), בערך 10^8 השוואות עבור 10^4 חבלים.
אלגוריתם
- מעתיקים את החבלים לרשימת עבודה,
pile, ומתחילים אתtotalבערך 0. - חוזרים על הפעולה עד שנותר חבל אחד: מוצאים את החבל הקצר ביותר ומסירים אותו על ידי העברת החבל האחרון למקומו.
- עושים זאת שוב כדי למצוא את החבל הקצר הבא.
- מוסיפים את הסכום של שניהם ל-
totalומוסיפים לערימה חבל באורך הזה. - מחזירים את
total.
def minCostRopes(ropes):
pile = list(ropes)
def take_shortest():
k = 0
for i in range(1, len(pile)):
if pile[i] < pile[k]:
k = i
pile[k], pile[-1] = pile[-1], pile[k] # move it to the end, then remove it
return pile.pop()
total = 0
while len(pile) > 1:
joined = take_shortest() + take_shortest()
total += joined
pile.append(joined)
return totalערימת מינימום
האינטואיציה
ערימת מינימום שומרת את החבל הקצר ביותר בשורש שלה, והוצאת השורש או הוספת חבל עולות O(log n). סבב כולל שתי הוצאות, שמספקות לך את שני החבלים הקצרים ביותר, והוספה אחת של החבל שחובר.
כדי לחבר n חבלים דרושות n-1 פעולות חיבור, שכל אחת מהן כוללת שלוש פעולות על הערימה, ולכן זמן הריצה הוא O(n log n): בערך 4 × 10^5 צעדים עבור 10^4 חבלים. הערימה אף פעם לא מכילה יותר מ-n חבלים.
אלגוריתם
- הכניסו כל אורך של חבל לערימת מינימום והגדירו
total = 0. - חזרו על הפעולה עד שנותר חבל אחד: הוציאו את שני החבלים הקצרים ביותר.
- הוסיפו את הסכום שלהם אל
totalוהכניסו את הסכום בחזרה לערימה. - החזירו את
total, שנשאר0כאשר היה רק חבל אחד.
import heapq
def minCostRopes(ropes):
heap = list(ropes)
heapq.heapify(heap) # a min-heap: heap[0] is the shortest rope
total = 0
while len(heap) > 1:
joined = heapq.heappop(heap) + heapq.heappop(heap)
total += joined
heapq.heappush(heap, joined)
return total
מלכודות ומקרי קצה
- מיון פעם אחת וחיבור של כל חבל לחבל מצטבר אחד. החבל המצטבר עשוי להתארך יותר מחבלים שעדיין לא השתמשת בהם: עבור
[2, 3, 4, 4]העלות היא 5 + 9 + 13 = 27, בעוד שחיבור שני החבלים הקצרים ביותר עולה 5 + 8 + 13 = 26. - השלכת החבל שחובר. אורכו חוזר לערימה ומשלמים עליו שוב בחיבור מאוחר יותר.
- החזרת האורך של החבל הסופי. עבור
[5, 2, 8, 3]אורך החבל האחרון הוא 18, אבל העלות היא 33. - שימוש בטעות בערימת מקסימום.
priority_queueב-C++ ו-BinaryHeapב-Rust מחזירות את הערך הגדול ביותר, אלא אם הופכים את הסדר.
שאלות נפוצות3
מהי סיבוכיות הזמן של בעיית החבלים בעלות מינימלית?
זמן של O(n log n) ומקום של O(n) באמצעות ערימת מינימום: n-1 חיבורים, כשכל אחד כולל שלוש פעולות ערימה של O(log n). סריקת כל הערימה כדי למצוא את שני החבלים הקצרים ביותר הופכת זאת ל־O(n²).
האם Minimum Cost of Ropes זהה לקידוד Huffman?
כן, זה אותו אלגוריתם. קידוד Huffman בונה קוד קידומת על ידי מיזוג שני הסמלים בעלי השכיחות הנמוכה ביותר שוב ושוב, והוא ממזער את סכום המכפלה של כל שכיחות בעומק שלה בעץ. כאן החבלים ממלאים את תפקיד הסמלים, ואורכיהם ממלאים את תפקיד השכיחויות, ולכן העלות הכוללת היא אותו סכום.
האם אפשר לפתור את בעיית העלות המינימלית של חבלים ללא ערימה?
כן, באמצעות שתי תורים. מייני את החבלים לתור אחד והוסיפי כל חבל שחובר לסוף התור השני. החבלים שחוברו יוצאים בסדר לא יורד, כך שהחבל הקצר ביותר שנותר נמצא בראש אחד התורים. לכן כל סבב הוא O(1), ועם אורכים של עד 100, מיון ספירה הופך את זמן הריצה ל־O(n).
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def minCostRopes(ropes):
# יש לכתוב כאן קודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
ropes = [5, 2, 8, 3]
הפלט הצפוי
33