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²).
هل الحد الأدنى لتكلفة الحبال هو نفسه ترميز هوفمان؟
نعم، إنها الخوارزمية نفسها. يبني ترميز هوفمان رمزًا بادئًا بدمج الرمزين الأقل تكرارًا مرارًا وتكرارًا، ويقلل مجموع حاصل ضرب تكرار كل رمز في عمقه في الشجرة. هنا تؤدي الحبال دور الرموز، وتؤدي أطوالها دور التكرارات، لذا فإن التكلفة الإجمالية هي ذلك المجموع نفسه.
هل يمكن حل مسألة أقل تكلفة للحبال دون استخدام كومة؟
نعم، باستخدام طابورين. رتّب الحبال في أحد الطابورين، وأضف كل حبل موصول إلى مؤخرة الطابور الثاني. تخرج الحبال الموصولة بترتيب غير تنازلي، لذا يكون أقصر حبل متبقٍ في مقدمة أحد الطابورين. تستغرق كل جولة عندئذٍ O(1)، ومع أطوال تصل إلى 100، يجعل الفرز بالعدّ وقت التنفيذ O(n).
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def minCostRopes(ropes):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
ropes = [5, 2, 8, 3]
الإخراج المتوقع
33