Koko Eating Bananas
لدى Koko عدد n من أكوام الموز، في الكومة i عدد piles[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 مدة 1 و2 و2 و1 ساعة: المجموع 6، وهذا يناسب. عند السرعة 4، تستغرق 1 و3 و2 و1، أي 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.
سؤال إضافي
مسألة التوأم: تأكل Koko أكوام الموز كاملةً بالترتيب، بحد أقصى k موزة في اليوم، خلال d أيام. ما أصغر قيمة لـ k، وما الذي يتغير في بحثك؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
ثبّت سرعة واحدة
k. كم ساعة يستغرق تناول كومة منpموزات بهذه السرعة، مع العلم أن كوكو لا تنتقل بين الأكوام خلال الساعة؟ كم ساعة يستغرق تناول جميع الأكوام؟إذا أنهت السرعة
kالعمل في الوقت المحدد، فستنجح كل سرعة أعلى منها أيضًا. تشكّل السرعات التي تحقق ذلك سلسلة متصلة تبدأ عند الإجابة.أجرِ بحثًا ثنائيًا على السرعات من 1 إلى أكبر كومة. احسب الساعات عند السرعة الوسطى في مرور واحد: إذا كان الوقت يتسع ضمن
h، فالإجابة لا تتجاوز السرعة الوسطى؛ وإلا فهي أكبر منها.
الحل
الإجابة هي سرعة، وليست موضعًا في المصفوفة، وهذا يُخفي بحثًا ثنائيًا. يستغرق التحقق من سرعة واحدة مرورًا واحدًا على الأكوام، وإذا أنهت السرعة k العمل في الوقت المحدد، فكل سرعة أكبر منها ستفعل ذلك أيضًا. لذا أجرِ بحثًا ثنائيًا عن السرعات من 1 إلى أكبر كومة: نحو 30 عملية تحقق بدلًا من ما يصل إلى مليار.
جرّب كل سرعة بدءًا من 1 تصاعديًا
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
لا تنتقل كوكو إلى كومة أخرى خلال ساعة، لذا فإن كومةً تضم p موزة تستغرق p / k ساعة بعد التقريب إلى الأعلى: 10 موزات بسرعة 4 تستغرق 3 ساعات. جرّب السرعات 1 و2 و3، وهكذا، وأعِد أول سرعة يكون مجموع الساعات عندها ضمن h. إنها الأصغر، لأن كل سرعة أبطأ منها لم تنجح، وتتوقف الحلقة عند سرعة أكبر كومة، حيث تستغرق كل كومة ساعة واحدة.
إذا كان m هو حجم أكبر كومة، فهذا يعني إجراء ما يصل إلى m فحصًا لـ n كومة: نحو 5 × 10^12 خطوة عند وجود 5000 كومة، يقترب حجم كل منها من 10^9، و h = 5000.
الخوارزمية
- اضبط
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البحث الثنائي عن السرعة
الفكرة
كلما زادت السرعة، استغرقت كل كومة العدد نفسه من الساعات أو أقل، لذا تكون إجابات السؤال «هل تُنهي هذه السرعة العمل في الوقت المحدد؟» هي لا، لا، لا، ثم نعم ابتداءً من الإجابة الصحيحة. يعثر البحث الثنائي على أول إجابة بنعم.
احتفظ بنطاق من lo إلى hi يحتوي دائمًا على الإجابة، بدءًا من 1 وأكبر كومة، إذ تستغرق هذه السرعة ساعة واحدة لكل كومة، وبالتالي تناسب الوقت المتاح. إذا كانت السرعة المتوسطة mid مناسبة، فالإجابة هي mid أو سرعة أبطأ، لذا عيّن hi = mid. وإذا لم تكن مناسبة، فكل سرعة أبطأ منها لن تنجح أيضًا، لذا عيّن lo = mid + 1. عندما يصل lo إلى hi، تكون هذه هي الإجابة.
في المثال الأول، يبدأ النطاق من 1 إلى 10. السرعة 5 مناسبة، فيصبح النطاق من 1 إلى 5؛ والسرعة 3 تستغرق 10 ساعات، فيصبح من 4 إلى 5؛ والسرعة 4 تستغرق 7 ساعات، فيصبح من 5 إلى 5.
الخوارزمية
- عيّن
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 بت، وقد يسمح المجموع الذي يلتفّ عند التجاوز بمرور سرعة بطيئة. احسب باستخدام 64 بت، أو توقّف بمجرد أن يتجاوز المجموعh. - التقريب إلى الأسفل. تعطي
10 / 4الناتج 2، لكن تلك الكومة تستغرق 3 ساعات. - بدء النطاق من 0. عندئذٍ يمكن أن تكون
midمساوية لـ 0، ويحدث قسمة على صفر عند حساب العدد. - تعيين
hi = mid - 1عندما تكونmidمناسبة. قد يؤدي ذلك إلى استبعاد الإجابة. - بدء
hiبقيمة أقل من أكبر كومة. عندما يكونhمساويًا لعدد الأكوام، تفشل كل سرعة أقل، ويعيد البحث إحداها.
أسئلة شائعة3
ما التعقيد الزمني لمسألة أكل كوكو للموز؟
يعمل البحث الثنائي في زمن O(n log m)، حيث إن n هو عدد الأكوام وm هو أكبر كومة: نحو log2(m) عملية تحقق، أي 30 عندما m = 10^9، وتقرأ كل عملية منها جميع الأكوام مرة واحدة. والمساحة الإضافية هي O(1).
ما الحدّان الأدنى والأعلى للسرعة؟
الحد الأعلى هو أكبر كومة: عنده يستغرق أكل كل كومة ساعة واحدة، وهذا يناسب الوقت دائمًا. الحد الأدنى هو 1، ويمكنك رفعه إلى العدد الإجمالي للموز مقسومًا على h، مع التقريب إلى الأعلى، لأن كوكو تأكل k موزات على الأكثر في الساعة.
كيف تقسم الأعداد الصحيحة وتقرّب الناتج إلى الأعلى؟
استخدم (p + k-1) / k مع القسمة الصحيحة. تؤدي إضافة k-1 إلى دفع أي باقٍ إلى ما بعد المضاعف التالي لـ k، بينما يبقى المضاعف الدقيق كما هو: عند السرعة 4، تعطي 10 الناتج 13 / 4 = 3، وتعطي 8 الناتج 11 / 4 = 2. لا حاجة إلى أعداد الفاصلة العائمة.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def minEatingSpeed(piles, h):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
piles = [4, 10, 7, 3] h = 6
الإخراج المتوقع
5