Koko Eating Bananas
لدى Koko عدد n من أكوام الموز، حيث يمثّل piles[i] عدد حبات الموز في الكومة i، ولديها h ساعة قبل عودة الحراس. تختار سرعة أكل واحدة k، وهي عدد صحيح من حبات الموز في الساعة، وتلتزم بها. في كل ساعة، تأكل k حبة موز من كومة واحدة؛ وإذا كان المتبقي في تلك الكومة أقل من k، فإنها تنهيها وتستريح حتى انقضاء الساعة. أعد أصغر سرعة k تتيح لها إنهاء جميع الأكوام خلال h ساعة.
الدالة
- pilesinteger-array
- عدد الموز في كل كومة
- hinteger
- عدد الساعات التي تمتلكها كوكو
- تُرجعinteger
- أقل سرعة أكل صحيحة، بوحدة موزة في الساعة، تُنهي كل كومة خلال h ساعة
القيود
1 ≤ piles.length ≤ 50001 ≤ piles[i] ≤ 109piles.length ≤ h ≤ 109، لذا يوجد حل دائمًا.
أمثلة
- المدخلات
- piles = [4, 10, 7, 3]h = 6
- المخرجات
- 5
- الشرح
- عند السرعة 5، تستغرق الأكوام 4 و10 و7 و3 ساعة واحدة وساعتين وساعتين وساعة واحدة: المجموع 6، وهذا يناسب. وعند السرعة 4، تستغرق ساعة واحدة و3 ساعات وساعتين وساعة واحدة، أي 7 ساعات، ساعة واحدة أكثر من اللازم.
- المدخلات
- piles = [30, 11, 23, 4, 20]h = 5
- المخرجات
- 30
- الشرح
- خمس أكوام وخمس ساعات تعني ساعة واحدة بالضبط لكل كومة، لذا يجب أن تكون السرعة كافية لإنهاء أكبر كومة، وهي 30، في ساعة واحدة. عند سرعة 29، ستحتاج تلك الكومة إلى ساعة ثانية.
- المدخلات
- piles = [5, 9, 2]h = 20
- المخرجات
- 1
- الشرح
- عند السرعة 1، تستغرق الأكوام 5 + 9 + 2 = 16 ساعة، وهذا أقل من 20 ساعة. لا توجد سرعة أبطأ من 1، لذا فالإجابة هي 1.
+22 اختبارات مخفية عند الإرسال
سؤال إضافي
مسألة توأم: لدى Koko عدد d من الأيام، وتأكل أكوامًا كاملة بالترتيب المعطى، وتأكل في اليوم أكبر عدد من الأكوام ضمن حد يومي قدره k موزة. ما أصغر قيمة لـ k، وأي جزأين من بحثك الثنائي يتغيران؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
ثبّت سرعة واحدة
k. كم ساعة يستغرق كومة منpموزة بهذه السرعة، مع العلم أن كوكو لا تنتقل بين الأكوام خلال الساعة؟ كم ساعة تستغرقها جميع الأكوام؟إذا كانت السرعة
kتُنهي المهمة في الوقت المحدد، فإن كل سرعة أكبر منها تُنهيها أيضًا. تشكّل السرعات المناسبة نطاقًا متصلًا يبدأ عند الإجابة.أجرِ بحثًا ثنائيًا على السرعات من 1 إلى أكبر كومة. احسب عدد الساعات عند السرعة الوسطى في مرور واحد: إذا كان العدد ضمن
h، فالإجابة لا تتجاوز السرعة الوسطى؛ وإلا فهي أكبر منها.
الحل
الإجابة هنا هي سرعة، وليست موضعًا في المصفوفة، وهذا ما يخفي البحث الثنائي. يستغرق التحقق من سرعة واحدة مرورًا واحدًا على الأكوام. كما أن نتائج التحقق مرتبة: إذا أنجزت السرعة k المهمة في الوقت المحدد، فستنجزها كل سرعة أكبر منها أيضًا. لذا يمكنك إجراء بحث ثنائي على السرعات من 1 إلى أكبر كومة، وستحتاج إلى نحو 30 عملية تحقق، بينما قد يتطلب اختبار السرعات واحدة تلو الأخرى مليار عملية.
جرّب كل سرعة بدءًا من 1 تصاعديًا
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
ابدأ بسؤال واحد: كم من الوقت يستغرق كومة من p موزة عند سرعة k؟ تأكل Koko بمعدل k في الساعة، ولا تنتقل إلى كومة أخرى خلال الساعة نفسها، لذا تستغرق الكومة p / k ساعة بعد التقريب إلى الأعلى. تستغرق كومة من 10 موزات بسرعة 4 ثلاث ساعات: 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).
لماذا ينجح البحث الثنائي في سرعة الأكل؟
يتطلب البحث الثنائي سؤالًا إجابته إما نعم أو لا، وتكون الإجابات مرتبة. «هل تستطيع Koko الانتهاء بسرعة k؟» هو أحد هذه الأسئلة: فالسرعة الأعلى لا تتطلب ساعات أكثر أبدًا، لأن p / k لكل كومة، بعد التقريب إلى الأعلى، لا يمكن إلا أن يتناقص مع زيادة k. لذا تفشل كل سرعة أقل من الإجابة، وتنجح كل سرعة تبدأ من الإجابة فما فوق، ويجد البحث الحد الفاصل.
ما الحدّان الأدنى والأعلى للسرعة؟
الحد الأعلى هو أكبر كومة: بهذه السرعة، تستغرق كل كومة ساعة واحدة بالضبط، وh لا يقل عن عدد الأكوام، لذا فهذا يناسب دائمًا. والسرعة الأعلى تحتاج أيضًا إلى ساعة واحدة لكل كومة، لذا لا فائدة من البحث عن سرعة أكبر منها. الحد الأدنى هو 1، ويمكنك تضييق النطاق إلى إجمالي عدد الموز مقسومًا على h، مع التقريب إلى الأعلى، لأن كوكو تأكل على الأكثر k موزة في الساعة.
كيف تقسم الأعداد الصحيحة وتقرّب الناتج إلى الأعلى؟
استخدم (p + k-1) / k مع القسمة الصحيحة. تؤدي إضافة k-1 إلى دفع أي باقٍ إلى ما بعد المضاعف التالي لـ k، بينما يبقى المضاعف التام في موضعه: عند السرعة 4، تعطي القيمة 10 13 / 4 = 3، وتعطي القيمة 8 عند السرعة 4 11 / 4 = 2. وهذا يجنبك استخدام الأعداد العشرية ذات الفاصلة العائمة، حيث قد تُقرَّب القيم الكبيرة بطريقة خاطئة.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def minEatingSpeed(piles, h):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
piles = [4, 10, 7, 3] h = 6
المتوقع
5