והפעם נדבר על שאלת 3139. LeetCode - Minimum Cost to Equalize Array הבאה:
נותנים לנו רשימת של מספרים. לדוגמה [2,3,3,3,5]. עלינו לגרום לכל המספרים, להפוך להיות בערך של המספר הגדול ביותר שנמצא ברשימת המספרים. את זה ניתן לעשות באמצעות פעולה של הוספת הערך 1 לכל המספרים, עד שהם יגיעו לערך הרצוי.
לדוגמה, נניח שאנחנו רוצים להפוך את המספר 2 למספר 5, אז אנחנו צריכים לעשות 2+1+1+1 = 5. דהיינו, אנחנו צריכים להוסיף 3 פעמים את הערך 1, למספר 2, כדי להפוך את המספר 2 למספר 5.
ובדוגמה הנ"ל [2,3,3,3,5], המספר הגדול ביותר ברשימה, הוא 5 ולכן אנחנו נרצה להפוך את כל המספרים לערך 5, דהיינו, שבסוף התהליך הרשימה תיראה כך: [5,5,5,5,5]. ולשם כך עלינו לעשות 9 פעולות של הוספת הערך 1, לכל אחד מהמספרים, כדי שבסופו של תהליך, כל הערכים יהיו זהים לערך של המספר הגדול ביותר.
את זה נעשה באמצעות פעולות ההוספה הבאות: [2+1+1+1, 3+1+1, 3+1+1, 3+1+1, 5]. דהיינו, באמצעות 9 פעולות הוספה של הערך 1, נוכל להפוך את כל הערכים שברשימה לערך הגדול ביותר, שהוא הערך 5.
דהיינו, אם אנחנו מבצעים בכל פעם פעולה אחת של הגדלה 1 בלבד, נעשה זאת לדוגמה בדרך הבאה:
![]()
בנוסף אומרים לנו את הדבר הבא: באפשרותך לבצע פעולה אחת בכל פעם, של הוספת הערך 1, כדי להגדיל את כל המספרים, לערך הגדול ביותר, דהיינו, לבצע 9 פעולות של הגדלה ב 1, כנ"ל. אבל כמו כן, באפשרותך בפעולה אחת, הגדלה של שני ערכים שונים ב 1. דהיינו, בבת אחת להוסיף בשני מקומות שונים, את הערך 1, כדי ליישר קו שהכל יהיה בערך הגבוה ביותר. לדוגמה כך:
![]()
או לדוגמה כך:
![]()
דהיינו, במקום 9 פעולות של הוספת הערך 1, במקום זה נוכל לבצע 5 פעולות של הוספת 1, כדי ליישר את כל הערכים לערך 5.
במהות, בכל פעולה, אנחנו מגדילים 2 ערכים שונים, כל אחד מהם מגדילים אותו בערך 1. כאשר בדוגמה הנ"ל, אנחנו 4 פעמים נעשה הגדלה של שני מספרים שונים בערך 1 ופעם אחת אחרונה, נגדיל רק ערך אחד בלבד, בערך 1, כי כבר אין ערכים נוספים שצריכים להגדיל.
ועד כאן הבנו, שיש לנו רשימת מספרים, שאנחנו צריכים "ליישר קו" להגדיל את כל הערכים לערך הגדול ביותר, באמצעות פעולת הוספה של הערך 1 עד שכל הערכים יהיו זהים ערך הגדול ביותר. ואנחנו יכולים לבצע את זה, או באמצעות פעולת הוספה של 1 בכל פעם, או של 2 פעולות הוספה של 1 בכל פעם.
וכאן העלילה מסתבכת. מביאים לנו 2 מספרים נוספים COST1 + COST2. דהיינו, לכל פעולת הוספה יש מחיר. אם נוסיף רק 1 בודד בכל פעם, תהיה לזה עלות של COST1. ואם נוסיף 1 בשני מקומות בו זמנית, תהיה לזה עלות של COST2.
לדוגמה, נניח שמחיר1 (COST1) הוא 2 אז אם נבצע 9 פעולות של הוספת 1, הרי שעלות ההוספות תהיה 18. ואם נניח שמחיר2 (COST2) הוא 1, אז בדוגמה הנ"ל נבצע 4 הוספות של מחיר2, דהיינו, עלות 4, כי לכל פעולת הוספה יש עלות של 1. ובנוסף נוסיף עוד עלות של מחיר1 שהיא 2. והרי שיש לנו עלות של 6.
כי בדוגמה הנ"ל עשינו 4 הוספות כפולות בעלות של מחיר2 שהוא 1. 4*1=4. ועשינו גם פעולה אחת של הוספה 1 שהיא בעלות של מחיר1 שהוא 2. ואז 4+2 = 6.
כמו בדוגמה שהם הביאו
בהינתן רשימת מספרים כלשהי באורך כלשהו, לדוגמה המספרים הבאים (ובכוונה אני מביא כאן רשימה ארוכה, כדי להמחיש את הקושי של השאלה)
[1, 42, 73, 18, 90, 55, 7, 29, 84, 12, 67, 3, 99, 50, 23, 88, 36, 61, 9, 77, 45, 14, 70, 2, 85, 31, 64, 6, 93, 38, 81, 16, 97, 53, 26, 71, 4, 89, 34, 59, 11, 66, 1, 44, 79, 21, 95, 51, 24, 87, 33, 68, 8, 74, 19, 92, 57, 13, 78, 30, 83, 17, 96, 52, 27, 72, 5, 90, 35, 60, 10, 65, 0, 43, 80, 22, 94, 49, 20, 86, 32, 67, 7, 75, 100, 98, 54, 28, 73, 3, 88, 39, 82, 16, 91, 56, 12, 76, 25, 69, 9, 94, 48, 21, 97, 50, 23, 89, 37, 62, 4, 79, 18, 93, 58, 14, 81, 28, 85]
ובהינתן מחיר1 + מחיר2 כלשהם, לדוגמה מחיר1 הוא 10 ומחיר2 הוא 15, במקרה כזה השאלה היא, מה יהיה המחיר המינימלי ההכרחי שנהיה חייבים לשלם, כדי להגדיל את כל המספרים למספר הגדול ביותר? עד כאן הפירוש של השאלה...
ועכשיו נצעד אל התשובה כך:
אז איך בעצם ניגשים לזה? אז לשם כך נחזור שוב על השאלה מההתחלה וננסה לחלק את כל התהליך לחלקים הכי קטנים, לדוגמה כך:
שואלים אותנו: נותנים לנו רשימת מספרים. עלינו להגדיל את כל רשימת המספרים, אל המספר הגדול ביותר ברשימה. עלינו לעשות זאת באמצעות פעולת הוספה של הערך 1, לכל אחד מהמספרים, עד שניישר קו של כל המספרים.
נעצור כאן לרגע אחד. האם עד כאן היינו יודעים איך לנתח את המצב הזה? תשובה: כנראה שכן. בתור התחלה, היינו מאתרים את המספר הגדול ביותר ברשימה. ואחר כך היינו מוספים את הערך 1 לכל אחד מהמספרים. היינו עושים זאת X פעמים, עד שהיינו מיישרים קו של כל המספרים.
עכשיו, נניח שהיו אומרים לנו, שלכל פעולת הוספה, יש מחיר1 כלשהו. והיו שואלים אותנו, כמה יעלה לנו להגדיל את כל המספרים? האם היינו יודעים לפתור את זה? תשובה: כן.
היינו פשוט סופרים את כל פעולות ההוספה של הערך 1. היינו מכפילים את כמות פעולות ההוספה בערך של מחיר1, והיינו מגיעים לעלות שלנו ליישר את כל המספרים כלפי מעלה.
ונעצור כאן לרגע וננתח את הנ"ל.
בעצם יש לנו כאן כמה שלבים.
שלב 1 - איתור המספר הגדול ביותר ברשימה. שלצורך העניין ברשימה הנ"ל המספר הגדול ביותר הוא 100.
שלב 2 - לעבור על כל המספרים, ולבצע פעולה של 100 פחות הערך בכל מיקום. וכך נקבל את כמות ההוספות שעלינו לבצע כדי להביא את המספר הנוכחי, אל הערך המקסימאלי, שהוא לצורך העניין 100.
שלב 3 - עלינו לעבור על כל הרשימה ולסכום את הכמות של כל פעולות ההוספה.
שלב 4 - עלינו להכפיל את כמות פעולות ההוספה, בעלות של מחיר1
וכך יש לנו את התוצאה, של מה העלות שלנו ליישר את כל הרשימה כלפי מעלה.
או שיכולנו גם בשלב 3 - לחשב את העלות של ליישר את המספר הנוכחי כלפי מעלה.
ובשלב 4 - לעבור על כל הרשימה ולסכום את כל העלויות.
עד כאן נראה שהדברים יחסית ברורים.
אני אציין ואומר, שבעצם יש לנו כאן במהות 2 תהליכים. 1 - איתור המספר הגדול ביותר. 2 - הגדלת כל המספרים וסכימה של הערכים וכולי.
האם ניתן לבצע את 2 התהליכים האלו תוך כדי ריצה אחת על הרשימה, או שצריך בשלב 1 לעבור על כל הרשימה, כדי לאתר את המספר הגדול ביותר. ורק אחר כך בשלב 2 לבצע את פעולות ההגדלה, הסכימה, ההכפלה וכולי?
אז לכאורה, אכן צריכים לרוץ על הרשימה, פעמיים. פעם ראשונה כדי לאתר את המספר הגדול ביותר. ורק אחר כך לעבור על כל הערכים להגדיל אותם וכולי.
אבל זאת לא כל האמת. כי בפועל, אפשרי לרוץ פעם אחת על כל הרשימה ולבצע בריצה אחת את הפעולות הבאות:
1 - לנסות לאתר כל המספר הגדול ביותר.
2 - באותה ריצה, לסכום את כל הערכים שיש לנו ברשימה. דהיינו, הערך במיקום 1 + הערך במיקום 2 + הערך במיקום 3 וכולי, כמו שהם, בלי לבצע שום חישוב נוסף.
בסוף ריצה אחת על כל הרשימה, נוכל לדעת מהו המספר הגדול ביותר.
ואז מכך נוכל לבצע חישוב של: הערך הגדול ביותר, כפול כמות המספרים ברשימה. ואז נוכל להסיק מכך את הערך המקסימאלי שהיה, אם כל הערכים ברשימה היו בגודל של הערך הגדול ביותר. לדוגמה במקרה הנ"ל, 50 ערכים 100 שהוא הערך הגדול ביותר, = 5000. עכשיו, אם נסכום את כל המספרים, אז נראה שהערך שלהם הוא X. ואז 5000 פחות X, זה בעצם ההפרש שבין הערכים הנוכחיים לבין מקרה שבו כל הערכים היו באותו הגודל המקסימאלי. ו ה X הזה, מייצג את כמות פעולות ההוספה שנצטרך לעשות, כדי להביא את כל המספרים לערך המקסימאלי שלהם.
ולתובנה הזאת, שניתן לחשב את הכל בריצה אחת, ניתן להגיע באמצעות ניסוי ידני, שבו פותרים את התרגיל שוב ושוב בצורה ידנית כמה פעמים.
נניח שהרשימה היא כזאת: [2,3,3,3,5] כנ"ל.
דהיינו:
MAX = 5
N = 5
אז לכאורה עלינו לבצע את הפעולות הבאות:
(5-2=3) + (5-3=2) + (5-3=2) + (5-3=2) = 9 פעולות
אבל מצד האמת, אפשרי לחשב זאת גם כך:
(5 * 5 = 25) דהיינו, המקסימאלי שהיה אם כל הערכים היו זהים לערך הגדול ביותר, שהוא 5 כנ"ל.
(2+3+3+3+5 = 16) דהיינו, סכום נוכחי של כל הערכים.
ואז: 25-16=9. דהיינו, עלינו לבצע 9 הגדלות, כדי ליישר את כל הערכים כלפי מעלה.
במילים אחרות, על ידי ניסוי ידני כמה פעמים של פתירת התרגיל הנ"ל, ניתן לראות שבזמן ריצה O(N) ניתן לפתור את התרגיל הנ"ל, כנ"ל. שניתן בריצה אחת, לאתר את המספר הגדול ביותר ולפתור את הכל.
ובעצם עד כה, לקחנו את השאלה המקורית וחילקנו אותה לחלקים. התחלנו במקרה שהוא יחסית קל, שבו יש לנו רק מחיר1 ועלינו לחשב את מחיר1 בלבד. וראינו שבעצם ניתן לעשות זאת בזמן ריצה שהוא O(N).
ועכשיו נמשיך לחלק לחלקים ונעבור לחלק קצת יותר קשה של השאלה, והוא, בהינתן רשימה של מספרים כנ"ל, ובהינתן אפשרות אחת ויחידה להגדיל את המספרים כנ"ל, והיא באמצעות הגדלת 2 מספרים בכל פעם בבת אחת. דהיינו, שאנחנו חייבים להגדיל בערך 1, אך ורק שני מספרים שונים בבת אחת. האם היינו יודעים לחשב את כמות הפעמים שניתן לבצע את פעולת ההגדלה הזאת?
ואסביר: נשים רגע אחד בצד את תהליך איתור המספר הגדול ביותר. נשים רגע אחד בצד גם את תהליך החישוב של העלות של ביצוע פעולות ההגדלה. ננסה לחשוב אך ורק על החלק של כמה פעמים ניתן לבצע פעולת הגדלה כפולה, שבה בבת אחת מגדילים שני מספרים בערך 1, עד שכל המספרים מגיעים לערך הגבוה ביותר. האם נדע איך לחשב את זה? כי אם לא, אז ממילא לא נוכל לפתור את השאלה הגדולה.
אז איך בעצם יודעים כמה פעמים ניתן לבצע הגדלה כפולה, דהיינו, שמגדילים שני ערכים בבת אחת? תשובה: נגיע לזה בהמשך.
אבל כרגע נחזור לנתח את השאלה המקורית.
אז בעצם עד כה, היה לנו תהליך של למצוא את המספר הגדול ביותר.
יש לנו גם תהליך של לחשב כמה פעמים נצטרך לבצע הגדלה של כל המספרים בכל פעם מספר אחד, עד למקסימום.
יש לנו גם תהליך של לחשב, כמה מקסימום פעמים נוכל לבצע הגדלה כפולה של שני ערכים בבת אחת.
ומכאן נובעת רמת הקושי הבאה של השאלה, שהיא, שיש לנו עוד חישוב אפשרי, לחשב, במידה ונבצע X הגדלות כפולות, כמה Y הגדלות בודדות נבצע.
דהיינו, אם יש לנו צורך להגדיל את כל המספרים נניח בסכום של 500. אז כעיקרון, במידה ונרצה לבצע כמה שיותר הגדלות כפולות, ורק לאחר מכן הגדלות בודדות, כמה פעמים נוכל לבצע הגדלות כפולות, לפני שנהיה חייבים לבצע הגדלות בודדות.
ואחרי שנדע את כל זה, עכשיו נוכל לחשב את העלות של כל ההגדלות.
עד כאן זה בעצם סיכום ביניים של מה שהבנו עד כה.
ועכשיו נעבור לחלק נוסף של השאלה, שעומד בפני עצמו, והוא, בהינתן לנו מחיר1 שהוא עלות של הגדלה בודדת ובהינתן לנו מחיר2 שהוא עלות של הגדלה כפולה, אז, מה יהיה המחיר המינימלי שנוכל לשלם, כדי להגדיל את כל המספרים.
ואיך ניגשים לפתור את החלק הזה של השאלה?
אז לשם כך לכאורה בעצם עלינו לקחת רשימה, לחשב את כל האפשרויות האפשריות להגדיל את הרשימה למקסימום. באמצעות כל השילובים של הגדלה בודדת ושל הגדלה כפולה. ומכאן נוכל לדעת, מהו המחיר המינימלי שעלינו לשלם כדי להגדיל את הרשימה כולה.
אבל זהו כמובן חישוב לא יעיל מבחינת זמן ריצה.
ולכן, אם היינו יודעים מראש, איך הכי יעיל למלא את הרשימה, אז היה יותר קל לחשב את העלות.
דהיינו, אם ננתח את כל האפשרויות, נראה שבסופו של דבר, יש רק 3 אפשרויות אפשריות. שהן:
מבחינת המחיר שנשלם:
1 - זה לא משנה אם נבצע הגדלה בודדת או הגדלה כפולה.
2 - זה כן משנה ולכן עלינו לבצע כמה שיותר, הגדלות כפולות ורק לאחר מכן הגדלות בודדות.
3 - זה כן משנה ולכן עלינו לבצע אך ורק הגדלות בודדות.
ומאחר שבסופו של דבר, יש רק 3 אפשרויות בלבד, לכן איך בעצם ניגשים לזה?
אז אם נעשה קצת סימולציות באופן ידני וננסה למצוא את החוקיות, נראה שהחישוב הוא כך:
אם מחיר1 * 2 הוא קטן ממחיר2, אז בכל מקרה עדיף תמיד לעשות הגדלות בודדות.
אם מחיר1 * 2 הוא זהה למחיר2, אז זה לא משנה איך נבצע את ההגדלות בצורה בודדת או כפולה.
אם מחיר1 * 2 הוא גדול ממחיר2, אז בכל מקרה עדיף תמיד קודם כל לעשות כמה שיותר הגדלות כפולות ורק אחר כך בלית ברירה, לעשות הגדלות בודדות.
לדוגמה:
אם נניח מחיר1 של הגדלה בודדת אחת, הוא 100 והמחיר2 של הגדלה כפולה הוא 1, אז ברור שנעדיף לשלם כמה שפחות ולבצע כמה שיותר הגדלות כפולות. אבל אם מחיר2 הוא 100 ומחיר1 הוא 1, אז ברור שנעדיף לבצע כמה שיותר הגדלות בודדות. ואם מחיר1 הוא 1 ומחיר2 הוא 2, אז זה לא משנה איך נבצע את ההגדלות.
או במילים אחרות, מכך נוכל להסיק לגבי פתרון השאלה המקורית את הדבר הבא:
בהינתן רשימת מספרים, שעלינו להגדיל אותה למקסימום ב 2 דרכים אפשרויות עם 2 מחירים שונים. אז בשלב הראשון עלינו להבין האם כדאי לנו לבצע כמה שיותר הגדלות בודדות או כפולות, באמצעות חישוב המחיר כנ"ל.
ואז, אם עלינו לבצע כמה שיותר הגדלות בודדות, או במידה וזה לא משנה איך נבצע את ההגדלות, אז נוכל לפתור את התרגיל כנ"ל, כי בעצם מבחינתנו נוכל לומר שיש רק אפשרות אחת, של הגדלה בודדת, של מחיר1. שאת המצב הזה אנחנו יודעים לפתור כנ"ל.
אבל אם ורק אם נגלה, שמחיר2 של הגדלה כפולה, הוא קטן ממחיר1 כפול 2, דהיינו, שאז אנחנו נרצה לבצע כמה שיותר הגדלות כפולות ורק אחר כך בודדות, אז בעצם אנחנו נצטרך לדעת, איך יודעים כמה הגדלות כפולות ניתן לבצע.
ואז, ניקח את סך כל ההגדלות שצריך לבצע, נניח 500. ונניח שניתן לבצע מתוך זה 100 הגדלות כפולות. אז נוכל להסיק, שנעשה 100 הגדלות כפולות (סה"כ 200) ונצטרך לבצע עוד 300 הגדלות בודדות. ומכך נוכל לחשב את העלות המינימלית, בהכפלה של מחיר1 + מחיר2 בהתאם.
במילים אחרות, כרגע ניתן להבין שבעצם כדי לפצח את השאלה המקורית, בסך הכל עלינו לגלות איך יודעים כמה מקסימום הגדלות כפולות ניתן לבצע. אז איך ניגשים לזה?
אז איך ניגשים לזה?
אז נתחיל מהמקרה הקל ביותר, נניח שיש לנו את הרשימה הבאה [1,2] דהיינו, שאנחנו צריכים להגדיל את 1 לערך 2. האם ניתן לבצע זאת בהגדלה כפולה? כמובן שלא. אפשרי לבצע זאת בהגדלה אחת בודדת בלבד.
ואם יש לנו את הרשימה [1, 100] דהיינו, שאנחנו צריכים להגדיל את הערך 1 לערך 100. האם ניתן לעשות זאת בהגדלות כפולות? תשובה: לא. רק ב 99 הגדלות בודדות.
או במילים אחרות, בטוח נכון שכאשר צריכים להגדיל רק עמודה אחת בודדת, הרי שאין אפשרות לבצע הגדלה כפולה.
ומה אם יש לנו להגדיל 2 עמודות, לדוגמה [1, 1, 2], שעלינו להגדיל את 2 העמודות של ה 1 אל הערך 2. הרי שניתן לבצע כאן הגדלה אחת כפולה שתהפוך את כל הרשימה ל [2, 2, 2].
ואם יש לנו רשימה של [1, 1, 100]. במקרה כזה נוכל לבצע 99 הגדלות כפולות, שיביאו את הרשימה ל [100,100,100].
ואם לצורך העניין נצטרך להגדיל 3 עמודות, לדוגמה [1,1,1,2], הרי שבמקרה כזה, נוכל לבצע הגדלה 1 כפולה, שתביא אותנו ל [2,2,1,2] ואז נצטרך לבצע עוד הגדלה בודדת כדי ליישר את כל הרשימה ל [2,2,2,2].
ומה יקרה אם תהיה לנו רשימה כזאת [1,1,1,100] כמה הגדלות כפולות נוכל לבצע עכשיו? אז אם נבדוק נראה שאנחנו צריכים לבצע 99*3 הגדלות. דהיינו, 297 הגדלות. ואת זה ניתן לבצע באמצעות, 148 הגדלות כפולות + הגדלה אחת בודדת.
אז לכאורה מצאנו לנו חוקיות מסוימת, שאומרת, ניקח את כמות ההגדלות שצריך לבצע בסך הכל ונחלק אותה ל 2. וזאת תהיה כמות ההגדלות הכפולות שניתן לבצע. את השארית, נגדיל בצורה של הגדלה בודדת.
ומכך נובע ש, בהינתן עמודות שוות בגובהן, שצריך להגדיל את כולן באותה כמות הגדלות, אז:
אם יש לנו מספר זוגי של עמודות שצריכים להגדיל, לדוגמה:
[1,1,100]
[1,1,1,1,100]
[1,1,1,1,1,1,100]
[1,1,1,1,1,1,1,1,100]
אז ניקח את סה"כ ההגדלות שצריכים לבצע, נחלק ל 2 ונקבל את כמות ההגדלות הכפולות שצריכים לבצע.
ואם יש לנו מספר אי זוגי של עמודות שצריכים להגדיל, לדוגמה:
[1,100]
[1,1,1,100]
[1,1,1,1,1,100]
[1,1,1,1,1,1,1,100]
אז נצטרך לבצע את החישוב הבא:
אם כמות ההגדלות שצריך לבצע, היא עצמה זוגית, דהיינו, לדוגמה במקרים הבאים:
[2,100]
[2,2,2,100]
[2,2,2,2,2,100]
[2,2,2,2,2,2,2,100]
שצריכים להגדיל את כל המספרים ב 98 שזה מספר זוגי, אז שוב כנ"ל, ניקח את סה"כ ההגדלות שצריכים לבצע, לחלק ל 2. וזו תהיה כמות ההגדלות הכפולות שניתן לבצע.
אבל אם נצטרך להגדיל את המספרים בערך אי זוגי וכמות המספרים עצמם שנצטרך להגדיל תהיה אי זוגית, לדוגמה:
[1,100]
[1,1,1,100]
[1,1,1,1,1,100]
[1,1,1,1,1,1,1,100]
שיש לנו כמות אי זוגית של עמודות שצריכים להגדיל + צריכים להגדיל כל עמודה ב 99, שזה מספר אי זוגי, אז במקרה כזה, ניקח את סה"כ הסכום שצריך להגדיל, נחלק אותו ב 2. וזו תהיה כמות ההגדלות הכפולות שצריכים לבצע. ואחר כך בוודאות שנצטרך לבצע עוד הגדלה אחת בודדת של השארית.
אבל כל מה שאמרנו עד כאן, נכון, אבל באופן חלקי.
ניקח לדוגמה מבני עמודות כאלו:
![]()
את כל המבני האלו, נוכל לפתור אותם בהגדלות כפולות ללא בעיה כנ"ל.
ומה לגבי מבנה כזה:
![]()
גם אותו נוכל לפתור בהגדלות כפולות.
אבל מה לגבי מבנה כזה:
![]()
מבנה כזה, נוכל לפתור אותו ב 2 הגדלות כפולות + הגדלה 1 בודדת.
ומה לגבי מבנים כאלו?
![]()
גם אותם לא נוכל לפתור בהגדלות כפולות, אלא נצטרך כמות של הגדלות בודדות.
אז מה החוקיות כאן?
אז נסתכל לדוגמה על המקרים הבאים:
![]()
נראה שבכולם, כן ניתן למלא את הכל בהגדלות כפולות.
ואם נסתכל על המקרים הבאים:
![]()
נראה שגם בהם ניתן למלא את כל העמודות עם הגדלה כפולה + בחלק מהמקרים עם הגדלה בודדת כלשהי.
אז אם נשחק שוב בצורה ידנית עם המון מקרים, נראה שיש כאן את החוקיות הבאה:
אז החוקיות אומרת כך:
כאשר אנחנו באים לנתח את כמות ההגדלות הכפולות שאנחנו יכולים לבצע, עלינו לאתר את העמודה עם הערך הקטן ביותר, שאותה אנחנו הכי צריכים להגדיל.
דהיינו, בדיוק כמו שאנחנו מחפשים את הערך MAX שהוא הערך שאליו צריכים להגדיל את כל המספרים, כך עלינו לחפש את הערך MIN, שהיא העמודה עם המספר הקטן ביותר, שבה אנחנו צריכים לבצע את כמות ההגדלות הגדולה ביותר.
עכשיו, יתכן שיש כמה עמודות עם הערך MIN. בדיוק כמו שיתכן שיש כמה עמודות עם הערך MAX. אבל לצורך העניין כרגע זה לא מעניין אותנו. כן מעניין אותנו לאתר את הערך MIN. שבו בעצם צריכים לבצע מקסימום פעולות הגדלה כדי להביא אותו לערך MAX.
עכשיו, אם ננתח בצורה ידנית המון מקרים, נראה כי בעצם בהינתן רשימת מספרים כלשהי, הרי שיש לנו עמודה אחת או יותר של הערך MAX. ויש לנו עמודה אחת או יותר...
You are given an integer array nums and two integers cost1 and cost2. You are allowed to perform either of the following operations any number of times:
Choose an index i from nums and increase nums[i] by 1 for a cost of cost1.
Choose two different indices i, j, from nums and increase nums[i] and nums[j] by 1 for a cost of cost2.
Return the minimum cost required to make all elements in the array equal.
Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: nums = [4,1], cost1 = 5, cost2 = 2
Output: 15
Explanation:
The following operations can be performed to make the values equal:
Increase nums[1] by 1 for a cost of 5. nums becomes [4,2].
Increase nums[1] by 1 for a cost of 5. nums becomes [4,3].
Increase nums[1] by 1 for a cost of 5. nums becomes [4,4].
The total cost is 15.
Example 2:
Input: nums = [2,3,3,3,5], cost1 = 2, cost2 = 1
Output: 6
Explanation:
The following operations can be performed to make the values equal:
Increase nums[0] and nums[1] by 1 for a cost of 1. nums becomes [3,4,3,3,5].
Increase nums[0] and nums[2] by 1 for a cost of 1. nums becomes [4,4,4,3,5].
Increase nums[0] and nums[3] by 1 for a cost of 1. nums becomes [5,4,4,4,5].
Increase nums[1] and nums[2] by 1 for a cost of 1. nums becomes [5,5,5,4,5].
Increase nums[3] by 1 for a cost of 2. nums becomes [5,5,5,5,5].
The total cost is 6.
Example 3:
Input: nums = [3,5,3], cost1 = 1, cost2 = 3
Output: 4
Explanation:
The following operations can be performed to make the values equal:
Increase nums[0] by 1 for a cost of 1. nums becomes [4,5,3].
Increase nums[0] by 1 for a cost of 1. nums becomes [5,5,3].
Increase nums[2] by 1 for a cost of 1. nums becomes [5,5,4].
Increase nums[2] by 1 for a cost of 1. nums becomes [5,5,5].
The total cost is 4.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 106
1 <= cost1 <= 106
1 <= cost2 <= 106
אז קודם כל נסביר את השאלה שהולכת כך:Choose an index i from nums and increase nums[i] by 1 for a cost of cost1.
Choose two different indices i, j, from nums and increase nums[i] and nums[j] by 1 for a cost of cost2.
Return the minimum cost required to make all elements in the array equal.
Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: nums = [4,1], cost1 = 5, cost2 = 2
Output: 15
Explanation:
The following operations can be performed to make the values equal:
Increase nums[1] by 1 for a cost of 5. nums becomes [4,2].
Increase nums[1] by 1 for a cost of 5. nums becomes [4,3].
Increase nums[1] by 1 for a cost of 5. nums becomes [4,4].
The total cost is 15.
Example 2:
Input: nums = [2,3,3,3,5], cost1 = 2, cost2 = 1
Output: 6
Explanation:
The following operations can be performed to make the values equal:
Increase nums[0] and nums[1] by 1 for a cost of 1. nums becomes [3,4,3,3,5].
Increase nums[0] and nums[2] by 1 for a cost of 1. nums becomes [4,4,4,3,5].
Increase nums[0] and nums[3] by 1 for a cost of 1. nums becomes [5,4,4,4,5].
Increase nums[1] and nums[2] by 1 for a cost of 1. nums becomes [5,5,5,4,5].
Increase nums[3] by 1 for a cost of 2. nums becomes [5,5,5,5,5].
The total cost is 6.
Example 3:
Input: nums = [3,5,3], cost1 = 1, cost2 = 3
Output: 4
Explanation:
The following operations can be performed to make the values equal:
Increase nums[0] by 1 for a cost of 1. nums becomes [4,5,3].
Increase nums[0] by 1 for a cost of 1. nums becomes [5,5,3].
Increase nums[2] by 1 for a cost of 1. nums becomes [5,5,4].
Increase nums[2] by 1 for a cost of 1. nums becomes [5,5,5].
The total cost is 4.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 106
1 <= cost1 <= 106
1 <= cost2 <= 106
נותנים לנו רשימת של מספרים. לדוגמה [2,3,3,3,5]. עלינו לגרום לכל המספרים, להפוך להיות בערך של המספר הגדול ביותר שנמצא ברשימת המספרים. את זה ניתן לעשות באמצעות פעולה של הוספת הערך 1 לכל המספרים, עד שהם יגיעו לערך הרצוי.
לדוגמה, נניח שאנחנו רוצים להפוך את המספר 2 למספר 5, אז אנחנו צריכים לעשות 2+1+1+1 = 5. דהיינו, אנחנו צריכים להוסיף 3 פעמים את הערך 1, למספר 2, כדי להפוך את המספר 2 למספר 5.
ובדוגמה הנ"ל [2,3,3,3,5], המספר הגדול ביותר ברשימה, הוא 5 ולכן אנחנו נרצה להפוך את כל המספרים לערך 5, דהיינו, שבסוף התהליך הרשימה תיראה כך: [5,5,5,5,5]. ולשם כך עלינו לעשות 9 פעולות של הוספת הערך 1, לכל אחד מהמספרים, כדי שבסופו של תהליך, כל הערכים יהיו זהים לערך של המספר הגדול ביותר.
את זה נעשה באמצעות פעולות ההוספה הבאות: [2+1+1+1, 3+1+1, 3+1+1, 3+1+1, 5]. דהיינו, באמצעות 9 פעולות הוספה של הערך 1, נוכל להפוך את כל הערכים שברשימה לערך הגדול ביותר, שהוא הערך 5.
דהיינו, אם אנחנו מבצעים בכל פעם פעולה אחת של הגדלה 1 בלבד, נעשה זאת לדוגמה בדרך הבאה:
בנוסף אומרים לנו את הדבר הבא: באפשרותך לבצע פעולה אחת בכל פעם, של הוספת הערך 1, כדי להגדיל את כל המספרים, לערך הגדול ביותר, דהיינו, לבצע 9 פעולות של הגדלה ב 1, כנ"ל. אבל כמו כן, באפשרותך בפעולה אחת, הגדלה של שני ערכים שונים ב 1. דהיינו, בבת אחת להוסיף בשני מקומות שונים, את הערך 1, כדי ליישר קו שהכל יהיה בערך הגבוה ביותר. לדוגמה כך:
או לדוגמה כך:
דהיינו, במקום 9 פעולות של הוספת הערך 1, במקום זה נוכל לבצע 5 פעולות של הוספת 1, כדי ליישר את כל הערכים לערך 5.
במהות, בכל פעולה, אנחנו מגדילים 2 ערכים שונים, כל אחד מהם מגדילים אותו בערך 1. כאשר בדוגמה הנ"ל, אנחנו 4 פעמים נעשה הגדלה של שני מספרים שונים בערך 1 ופעם אחת אחרונה, נגדיל רק ערך אחד בלבד, בערך 1, כי כבר אין ערכים נוספים שצריכים להגדיל.
ועד כאן הבנו, שיש לנו רשימת מספרים, שאנחנו צריכים "ליישר קו" להגדיל את כל הערכים לערך הגדול ביותר, באמצעות פעולת הוספה של הערך 1 עד שכל הערכים יהיו זהים ערך הגדול ביותר. ואנחנו יכולים לבצע את זה, או באמצעות פעולת הוספה של 1 בכל פעם, או של 2 פעולות הוספה של 1 בכל פעם.
וכאן העלילה מסתבכת. מביאים לנו 2 מספרים נוספים COST1 + COST2. דהיינו, לכל פעולת הוספה יש מחיר. אם נוסיף רק 1 בודד בכל פעם, תהיה לזה עלות של COST1. ואם נוסיף 1 בשני מקומות בו זמנית, תהיה לזה עלות של COST2.
לדוגמה, נניח שמחיר1 (COST1) הוא 2 אז אם נבצע 9 פעולות של הוספת 1, הרי שעלות ההוספות תהיה 18. ואם נניח שמחיר2 (COST2) הוא 1, אז בדוגמה הנ"ל נבצע 4 הוספות של מחיר2, דהיינו, עלות 4, כי לכל פעולת הוספה יש עלות של 1. ובנוסף נוסיף עוד עלות של מחיר1 שהיא 2. והרי שיש לנו עלות של 6.
כי בדוגמה הנ"ל עשינו 4 הוספות כפולות בעלות של מחיר2 שהוא 1. 4*1=4. ועשינו גם פעולה אחת של הוספה 1 שהיא בעלות של מחיר1 שהוא 2. ואז 4+2 = 6.
כמו בדוגמה שהם הביאו
Example 2:
Input: nums = [2,3,3,3,5], cost1 = 2, cost2 = 1
Output: 6
Explanation:
The following operations can be performed to make the values equal:
Increase nums[0] and nums[1] by 1 for a cost of 1. nums becomes [3,4,3,3,5].
Increase nums[0] and nums[2] by 1 for a cost of 1. nums becomes [4,4,4,3,5].
Increase nums[0] and nums[3] by 1 for a cost of 1. nums becomes [5,4,4,4,5].
Increase nums[1] and nums[2] by 1 for a cost of 1. nums becomes [5,5,5,4,5].
Increase nums[3] by 1 for a cost of 2. nums becomes [5,5,5,5,5].
The total cost is 6.
ועכשיו השאלה הנשאלת היא כדלקמן:Input: nums = [2,3,3,3,5], cost1 = 2, cost2 = 1
Output: 6
Explanation:
The following operations can be performed to make the values equal:
Increase nums[0] and nums[1] by 1 for a cost of 1. nums becomes [3,4,3,3,5].
Increase nums[0] and nums[2] by 1 for a cost of 1. nums becomes [4,4,4,3,5].
Increase nums[0] and nums[3] by 1 for a cost of 1. nums becomes [5,4,4,4,5].
Increase nums[1] and nums[2] by 1 for a cost of 1. nums becomes [5,5,5,4,5].
Increase nums[3] by 1 for a cost of 2. nums becomes [5,5,5,5,5].
The total cost is 6.
בהינתן רשימת מספרים כלשהי באורך כלשהו, לדוגמה המספרים הבאים (ובכוונה אני מביא כאן רשימה ארוכה, כדי להמחיש את הקושי של השאלה)
[1, 42, 73, 18, 90, 55, 7, 29, 84, 12, 67, 3, 99, 50, 23, 88, 36, 61, 9, 77, 45, 14, 70, 2, 85, 31, 64, 6, 93, 38, 81, 16, 97, 53, 26, 71, 4, 89, 34, 59, 11, 66, 1, 44, 79, 21, 95, 51, 24, 87, 33, 68, 8, 74, 19, 92, 57, 13, 78, 30, 83, 17, 96, 52, 27, 72, 5, 90, 35, 60, 10, 65, 0, 43, 80, 22, 94, 49, 20, 86, 32, 67, 7, 75, 100, 98, 54, 28, 73, 3, 88, 39, 82, 16, 91, 56, 12, 76, 25, 69, 9, 94, 48, 21, 97, 50, 23, 89, 37, 62, 4, 79, 18, 93, 58, 14, 81, 28, 85]
ובהינתן מחיר1 + מחיר2 כלשהם, לדוגמה מחיר1 הוא 10 ומחיר2 הוא 15, במקרה כזה השאלה היא, מה יהיה המחיר המינימלי ההכרחי שנהיה חייבים לשלם, כדי להגדיל את כל המספרים למספר הגדול ביותר? עד כאן הפירוש של השאלה...
ועכשיו נצעד אל התשובה כך:
אז איך בעצם ניגשים לזה? אז לשם כך נחזור שוב על השאלה מההתחלה וננסה לחלק את כל התהליך לחלקים הכי קטנים, לדוגמה כך:
שואלים אותנו: נותנים לנו רשימת מספרים. עלינו להגדיל את כל רשימת המספרים, אל המספר הגדול ביותר ברשימה. עלינו לעשות זאת באמצעות פעולת הוספה של הערך 1, לכל אחד מהמספרים, עד שניישר קו של כל המספרים.
נעצור כאן לרגע אחד. האם עד כאן היינו יודעים איך לנתח את המצב הזה? תשובה: כנראה שכן. בתור התחלה, היינו מאתרים את המספר הגדול ביותר ברשימה. ואחר כך היינו מוספים את הערך 1 לכל אחד מהמספרים. היינו עושים זאת X פעמים, עד שהיינו מיישרים קו של כל המספרים.
עכשיו, נניח שהיו אומרים לנו, שלכל פעולת הוספה, יש מחיר1 כלשהו. והיו שואלים אותנו, כמה יעלה לנו להגדיל את כל המספרים? האם היינו יודעים לפתור את זה? תשובה: כן.
היינו פשוט סופרים את כל פעולות ההוספה של הערך 1. היינו מכפילים את כמות פעולות ההוספה בערך של מחיר1, והיינו מגיעים לעלות שלנו ליישר את כל המספרים כלפי מעלה.
ונעצור כאן לרגע וננתח את הנ"ל.
בעצם יש לנו כאן כמה שלבים.
שלב 1 - איתור המספר הגדול ביותר ברשימה. שלצורך העניין ברשימה הנ"ל המספר הגדול ביותר הוא 100.
שלב 2 - לעבור על כל המספרים, ולבצע פעולה של 100 פחות הערך בכל מיקום. וכך נקבל את כמות ההוספות שעלינו לבצע כדי להביא את המספר הנוכחי, אל הערך המקסימאלי, שהוא לצורך העניין 100.
שלב 3 - עלינו לעבור על כל הרשימה ולסכום את הכמות של כל פעולות ההוספה.
שלב 4 - עלינו להכפיל את כמות פעולות ההוספה, בעלות של מחיר1
וכך יש לנו את התוצאה, של מה העלות שלנו ליישר את כל הרשימה כלפי מעלה.
או שיכולנו גם בשלב 3 - לחשב את העלות של ליישר את המספר הנוכחי כלפי מעלה.
ובשלב 4 - לעבור על כל הרשימה ולסכום את כל העלויות.
עד כאן נראה שהדברים יחסית ברורים.
אני אציין ואומר, שבעצם יש לנו כאן במהות 2 תהליכים. 1 - איתור המספר הגדול ביותר. 2 - הגדלת כל המספרים וסכימה של הערכים וכולי.
האם ניתן לבצע את 2 התהליכים האלו תוך כדי ריצה אחת על הרשימה, או שצריך בשלב 1 לעבור על כל הרשימה, כדי לאתר את המספר הגדול ביותר. ורק אחר כך בשלב 2 לבצע את פעולות ההגדלה, הסכימה, ההכפלה וכולי?
אז לכאורה, אכן צריכים לרוץ על הרשימה, פעמיים. פעם ראשונה כדי לאתר את המספר הגדול ביותר. ורק אחר כך לעבור על כל הערכים להגדיל אותם וכולי.
אבל זאת לא כל האמת. כי בפועל, אפשרי לרוץ פעם אחת על כל הרשימה ולבצע בריצה אחת את הפעולות הבאות:
1 - לנסות לאתר כל המספר הגדול ביותר.
2 - באותה ריצה, לסכום את כל הערכים שיש לנו ברשימה. דהיינו, הערך במיקום 1 + הערך במיקום 2 + הערך במיקום 3 וכולי, כמו שהם, בלי לבצע שום חישוב נוסף.
בסוף ריצה אחת על כל הרשימה, נוכל לדעת מהו המספר הגדול ביותר.
ואז מכך נוכל לבצע חישוב של: הערך הגדול ביותר, כפול כמות המספרים ברשימה. ואז נוכל להסיק מכך את הערך המקסימאלי שהיה, אם כל הערכים ברשימה היו בגודל של הערך הגדול ביותר. לדוגמה במקרה הנ"ל, 50 ערכים 100 שהוא הערך הגדול ביותר, = 5000. עכשיו, אם נסכום את כל המספרים, אז נראה שהערך שלהם הוא X. ואז 5000 פחות X, זה בעצם ההפרש שבין הערכים הנוכחיים לבין מקרה שבו כל הערכים היו באותו הגודל המקסימאלי. ו ה X הזה, מייצג את כמות פעולות ההוספה שנצטרך לעשות, כדי להביא את כל המספרים לערך המקסימאלי שלהם.
ולתובנה הזאת, שניתן לחשב את הכל בריצה אחת, ניתן להגיע באמצעות ניסוי ידני, שבו פותרים את התרגיל שוב ושוב בצורה ידנית כמה פעמים.
נניח שהרשימה היא כזאת: [2,3,3,3,5] כנ"ל.
דהיינו:
MAX = 5
N = 5
אז לכאורה עלינו לבצע את הפעולות הבאות:
(5-2=3) + (5-3=2) + (5-3=2) + (5-3=2) = 9 פעולות
אבל מצד האמת, אפשרי לחשב זאת גם כך:
(5 * 5 = 25) דהיינו, המקסימאלי שהיה אם כל הערכים היו זהים לערך הגדול ביותר, שהוא 5 כנ"ל.
(2+3+3+3+5 = 16) דהיינו, סכום נוכחי של כל הערכים.
ואז: 25-16=9. דהיינו, עלינו לבצע 9 הגדלות, כדי ליישר את כל הערכים כלפי מעלה.
במילים אחרות, על ידי ניסוי ידני כמה פעמים של פתירת התרגיל הנ"ל, ניתן לראות שבזמן ריצה O(N) ניתן לפתור את התרגיל הנ"ל, כנ"ל. שניתן בריצה אחת, לאתר את המספר הגדול ביותר ולפתור את הכל.
ובעצם עד כה, לקחנו את השאלה המקורית וחילקנו אותה לחלקים. התחלנו במקרה שהוא יחסית קל, שבו יש לנו רק מחיר1 ועלינו לחשב את מחיר1 בלבד. וראינו שבעצם ניתן לעשות זאת בזמן ריצה שהוא O(N).
ועכשיו נמשיך לחלק לחלקים ונעבור לחלק קצת יותר קשה של השאלה, והוא, בהינתן רשימה של מספרים כנ"ל, ובהינתן אפשרות אחת ויחידה להגדיל את המספרים כנ"ל, והיא באמצעות הגדלת 2 מספרים בכל פעם בבת אחת. דהיינו, שאנחנו חייבים להגדיל בערך 1, אך ורק שני מספרים שונים בבת אחת. האם היינו יודעים לחשב את כמות הפעמים שניתן לבצע את פעולת ההגדלה הזאת?
ואסביר: נשים רגע אחד בצד את תהליך איתור המספר הגדול ביותר. נשים רגע אחד בצד גם את תהליך החישוב של העלות של ביצוע פעולות ההגדלה. ננסה לחשוב אך ורק על החלק של כמה פעמים ניתן לבצע פעולת הגדלה כפולה, שבה בבת אחת מגדילים שני מספרים בערך 1, עד שכל המספרים מגיעים לערך הגבוה ביותר. האם נדע איך לחשב את זה? כי אם לא, אז ממילא לא נוכל לפתור את השאלה הגדולה.
אז איך בעצם יודעים כמה פעמים ניתן לבצע הגדלה כפולה, דהיינו, שמגדילים שני ערכים בבת אחת? תשובה: נגיע לזה בהמשך.
אבל כרגע נחזור לנתח את השאלה המקורית.
אז בעצם עד כה, היה לנו תהליך של למצוא את המספר הגדול ביותר.
יש לנו גם תהליך של לחשב כמה פעמים נצטרך לבצע הגדלה של כל המספרים בכל פעם מספר אחד, עד למקסימום.
יש לנו גם תהליך של לחשב, כמה מקסימום פעמים נוכל לבצע הגדלה כפולה של שני ערכים בבת אחת.
ומכאן נובעת רמת הקושי הבאה של השאלה, שהיא, שיש לנו עוד חישוב אפשרי, לחשב, במידה ונבצע X הגדלות כפולות, כמה Y הגדלות בודדות נבצע.
דהיינו, אם יש לנו צורך להגדיל את כל המספרים נניח בסכום של 500. אז כעיקרון, במידה ונרצה לבצע כמה שיותר הגדלות כפולות, ורק לאחר מכן הגדלות בודדות, כמה פעמים נוכל לבצע הגדלות כפולות, לפני שנהיה חייבים לבצע הגדלות בודדות.
ואחרי שנדע את כל זה, עכשיו נוכל לחשב את העלות של כל ההגדלות.
עד כאן זה בעצם סיכום ביניים של מה שהבנו עד כה.
ועכשיו נעבור לחלק נוסף של השאלה, שעומד בפני עצמו, והוא, בהינתן לנו מחיר1 שהוא עלות של הגדלה בודדת ובהינתן לנו מחיר2 שהוא עלות של הגדלה כפולה, אז, מה יהיה המחיר המינימלי שנוכל לשלם, כדי להגדיל את כל המספרים.
ואיך ניגשים לפתור את החלק הזה של השאלה?
אז לשם כך לכאורה בעצם עלינו לקחת רשימה, לחשב את כל האפשרויות האפשריות להגדיל את הרשימה למקסימום. באמצעות כל השילובים של הגדלה בודדת ושל הגדלה כפולה. ומכאן נוכל לדעת, מהו המחיר המינימלי שעלינו לשלם כדי להגדיל את הרשימה כולה.
אבל זהו כמובן חישוב לא יעיל מבחינת זמן ריצה.
ולכן, אם היינו יודעים מראש, איך הכי יעיל למלא את הרשימה, אז היה יותר קל לחשב את העלות.
דהיינו, אם ננתח את כל האפשרויות, נראה שבסופו של דבר, יש רק 3 אפשרויות אפשריות. שהן:
מבחינת המחיר שנשלם:
1 - זה לא משנה אם נבצע הגדלה בודדת או הגדלה כפולה.
2 - זה כן משנה ולכן עלינו לבצע כמה שיותר, הגדלות כפולות ורק לאחר מכן הגדלות בודדות.
3 - זה כן משנה ולכן עלינו לבצע אך ורק הגדלות בודדות.
ומאחר שבסופו של דבר, יש רק 3 אפשרויות בלבד, לכן איך בעצם ניגשים לזה?
אז אם נעשה קצת סימולציות באופן ידני וננסה למצוא את החוקיות, נראה שהחישוב הוא כך:
אם מחיר1 * 2 הוא קטן ממחיר2, אז בכל מקרה עדיף תמיד לעשות הגדלות בודדות.
אם מחיר1 * 2 הוא זהה למחיר2, אז זה לא משנה איך נבצע את ההגדלות בצורה בודדת או כפולה.
אם מחיר1 * 2 הוא גדול ממחיר2, אז בכל מקרה עדיף תמיד קודם כל לעשות כמה שיותר הגדלות כפולות ורק אחר כך בלית ברירה, לעשות הגדלות בודדות.
לדוגמה:
אם נניח מחיר1 של הגדלה בודדת אחת, הוא 100 והמחיר2 של הגדלה כפולה הוא 1, אז ברור שנעדיף לשלם כמה שפחות ולבצע כמה שיותר הגדלות כפולות. אבל אם מחיר2 הוא 100 ומחיר1 הוא 1, אז ברור שנעדיף לבצע כמה שיותר הגדלות בודדות. ואם מחיר1 הוא 1 ומחיר2 הוא 2, אז זה לא משנה איך נבצע את ההגדלות.
או במילים אחרות, מכך נוכל להסיק לגבי פתרון השאלה המקורית את הדבר הבא:
בהינתן רשימת מספרים, שעלינו להגדיל אותה למקסימום ב 2 דרכים אפשרויות עם 2 מחירים שונים. אז בשלב הראשון עלינו להבין האם כדאי לנו לבצע כמה שיותר הגדלות בודדות או כפולות, באמצעות חישוב המחיר כנ"ל.
ואז, אם עלינו לבצע כמה שיותר הגדלות בודדות, או במידה וזה לא משנה איך נבצע את ההגדלות, אז נוכל לפתור את התרגיל כנ"ל, כי בעצם מבחינתנו נוכל לומר שיש רק אפשרות אחת, של הגדלה בודדת, של מחיר1. שאת המצב הזה אנחנו יודעים לפתור כנ"ל.
אבל אם ורק אם נגלה, שמחיר2 של הגדלה כפולה, הוא קטן ממחיר1 כפול 2, דהיינו, שאז אנחנו נרצה לבצע כמה שיותר הגדלות כפולות ורק אחר כך בודדות, אז בעצם אנחנו נצטרך לדעת, איך יודעים כמה הגדלות כפולות ניתן לבצע.
ואז, ניקח את סך כל ההגדלות שצריך לבצע, נניח 500. ונניח שניתן לבצע מתוך זה 100 הגדלות כפולות. אז נוכל להסיק, שנעשה 100 הגדלות כפולות (סה"כ 200) ונצטרך לבצע עוד 300 הגדלות בודדות. ומכך נוכל לחשב את העלות המינימלית, בהכפלה של מחיר1 + מחיר2 בהתאם.
במילים אחרות, כרגע ניתן להבין שבעצם כדי לפצח את השאלה המקורית, בסך הכל עלינו לגלות איך יודעים כמה מקסימום הגדלות כפולות ניתן לבצע. אז איך ניגשים לזה?
אז איך ניגשים לזה?
אז נתחיל מהמקרה הקל ביותר, נניח שיש לנו את הרשימה הבאה [1,2] דהיינו, שאנחנו צריכים להגדיל את 1 לערך 2. האם ניתן לבצע זאת בהגדלה כפולה? כמובן שלא. אפשרי לבצע זאת בהגדלה אחת בודדת בלבד.
ואם יש לנו את הרשימה [1, 100] דהיינו, שאנחנו צריכים להגדיל את הערך 1 לערך 100. האם ניתן לעשות זאת בהגדלות כפולות? תשובה: לא. רק ב 99 הגדלות בודדות.
או במילים אחרות, בטוח נכון שכאשר צריכים להגדיל רק עמודה אחת בודדת, הרי שאין אפשרות לבצע הגדלה כפולה.
ומה אם יש לנו להגדיל 2 עמודות, לדוגמה [1, 1, 2], שעלינו להגדיל את 2 העמודות של ה 1 אל הערך 2. הרי שניתן לבצע כאן הגדלה אחת כפולה שתהפוך את כל הרשימה ל [2, 2, 2].
ואם יש לנו רשימה של [1, 1, 100]. במקרה כזה נוכל לבצע 99 הגדלות כפולות, שיביאו את הרשימה ל [100,100,100].
ואם לצורך העניין נצטרך להגדיל 3 עמודות, לדוגמה [1,1,1,2], הרי שבמקרה כזה, נוכל לבצע הגדלה 1 כפולה, שתביא אותנו ל [2,2,1,2] ואז נצטרך לבצע עוד הגדלה בודדת כדי ליישר את כל הרשימה ל [2,2,2,2].
ומה יקרה אם תהיה לנו רשימה כזאת [1,1,1,100] כמה הגדלות כפולות נוכל לבצע עכשיו? אז אם נבדוק נראה שאנחנו צריכים לבצע 99*3 הגדלות. דהיינו, 297 הגדלות. ואת זה ניתן לבצע באמצעות, 148 הגדלות כפולות + הגדלה אחת בודדת.
אז לכאורה מצאנו לנו חוקיות מסוימת, שאומרת, ניקח את כמות ההגדלות שצריך לבצע בסך הכל ונחלק אותה ל 2. וזאת תהיה כמות ההגדלות הכפולות שניתן לבצע. את השארית, נגדיל בצורה של הגדלה בודדת.
ומכך נובע ש, בהינתן עמודות שוות בגובהן, שצריך להגדיל את כולן באותה כמות הגדלות, אז:
אם יש לנו מספר זוגי של עמודות שצריכים להגדיל, לדוגמה:
[1,1,100]
[1,1,1,1,100]
[1,1,1,1,1,1,100]
[1,1,1,1,1,1,1,1,100]
אז ניקח את סה"כ ההגדלות שצריכים לבצע, נחלק ל 2 ונקבל את כמות ההגדלות הכפולות שצריכים לבצע.
ואם יש לנו מספר אי זוגי של עמודות שצריכים להגדיל, לדוגמה:
[1,100]
[1,1,1,100]
[1,1,1,1,1,100]
[1,1,1,1,1,1,1,100]
אז נצטרך לבצע את החישוב הבא:
אם כמות ההגדלות שצריך לבצע, היא עצמה זוגית, דהיינו, לדוגמה במקרים הבאים:
[2,100]
[2,2,2,100]
[2,2,2,2,2,100]
[2,2,2,2,2,2,2,100]
שצריכים להגדיל את כל המספרים ב 98 שזה מספר זוגי, אז שוב כנ"ל, ניקח את סה"כ ההגדלות שצריכים לבצע, לחלק ל 2. וזו תהיה כמות ההגדלות הכפולות שניתן לבצע.
אבל אם נצטרך להגדיל את המספרים בערך אי זוגי וכמות המספרים עצמם שנצטרך להגדיל תהיה אי זוגית, לדוגמה:
[1,100]
[1,1,1,100]
[1,1,1,1,1,100]
[1,1,1,1,1,1,1,100]
שיש לנו כמות אי זוגית של עמודות שצריכים להגדיל + צריכים להגדיל כל עמודה ב 99, שזה מספר אי זוגי, אז במקרה כזה, ניקח את סה"כ הסכום שצריך להגדיל, נחלק אותו ב 2. וזו תהיה כמות ההגדלות הכפולות שצריכים לבצע. ואחר כך בוודאות שנצטרך לבצע עוד הגדלה אחת בודדת של השארית.
אבל כל מה שאמרנו עד כאן, נכון, אבל באופן חלקי.
ניקח לדוגמה מבני עמודות כאלו:
את כל המבני האלו, נוכל לפתור אותם בהגדלות כפולות ללא בעיה כנ"ל.
ומה לגבי מבנה כזה:
גם אותו נוכל לפתור בהגדלות כפולות.
אבל מה לגבי מבנה כזה:
מבנה כזה, נוכל לפתור אותו ב 2 הגדלות כפולות + הגדלה 1 בודדת.
ומה לגבי מבנים כאלו?
גם אותם לא נוכל לפתור בהגדלות כפולות, אלא נצטרך כמות של הגדלות בודדות.
אז מה החוקיות כאן?
אז נסתכל לדוגמה על המקרים הבאים:
נראה שבכולם, כן ניתן למלא את הכל בהגדלות כפולות.
ואם נסתכל על המקרים הבאים:
נראה שגם בהם ניתן למלא את כל העמודות עם הגדלה כפולה + בחלק מהמקרים עם הגדלה בודדת כלשהי.
אז אם נשחק שוב בצורה ידנית עם המון מקרים, נראה שיש כאן את החוקיות הבאה:
אז החוקיות אומרת כך:
כאשר אנחנו באים לנתח את כמות ההגדלות הכפולות שאנחנו יכולים לבצע, עלינו לאתר את העמודה עם הערך הקטן ביותר, שאותה אנחנו הכי צריכים להגדיל.
דהיינו, בדיוק כמו שאנחנו מחפשים את הערך MAX שהוא הערך שאליו צריכים להגדיל את כל המספרים, כך עלינו לחפש את הערך MIN, שהיא העמודה עם המספר הקטן ביותר, שבה אנחנו צריכים לבצע את כמות ההגדלות הגדולה ביותר.
עכשיו, יתכן שיש כמה עמודות עם הערך MIN. בדיוק כמו שיתכן שיש כמה עמודות עם הערך MAX. אבל לצורך העניין כרגע זה לא מעניין אותנו. כן מעניין אותנו לאתר את הערך MIN. שבו בעצם צריכים לבצע מקסימום פעולות הגדלה כדי להביא אותו לערך MAX.
עכשיו, אם ננתח בצורה ידנית המון מקרים, נראה כי בעצם בהינתן רשימת מספרים כלשהי, הרי שיש לנו עמודה אחת או יותר של הערך MAX. ויש לנו עמודה אחת או יותר...
050-3331-331