Chocolate Distribution Problem
لديك بعض عبوات الشوكولاتة، ويمثل packets[i] عدد قطع الشوكولاتة في العبوة i. يحصل كل طالب من بين m طلاب على عبوة واحدة بالضبط، لذلك ستُوزَّع m عبوات مختلفة. اخترها بحيث يكون الفرق بين أكبر عبوة وأصغر عبوة من العبوات الموزعة أقل ما يمكن.
اكتب دالة باسم minDifference تُرجع أصغر فرق ممكن.
الدالة
- packetsinteger-array
- عدد قطع الشوكولاتة في كل عبوة
- minteger
- عدد الطلاب، يحصل كلٌّ منهم على حزمة واحدة
- تُرجعinteger
- أصغر فرق ممكن بين أكبر وأصغر طرد يتم توزيعه
القيود
2 ≤ m ≤ packets.length ≤ 1041 ≤ packets[i] ≤ 105- يمكن أن تحتوي عبوتان على العدد نفسه من قطع الشوكولاتة.
أمثلة
- المدخلات
- packets = [9, 3, 15, 7, 11, 4]m = 3
- المخرجات
- 4
- الشرح
- بعد الترتيب، تصبح الحزم 3 و4 و7 و9 و11 و15. تعطي كل من 3 و4 و7 و7 و9 و11 فرقًا مقداره
4، ولا توجد ثلاث حزم أقرب إلى بعضها.
- المدخلات
- packets = [20, 5, 18, 6, 19]m = 2
- المخرجات
- 1
- الشرح
- يختلف 5 و6 بمقدار 1، وكذلك 18 و19، و19 و20. لا توجد حزمتان متساويتان، لذا لا يمكن لأي زوج أن يحقق نتيجة أفضل من 1.
- المدخلات
- packets = [8, 1, 5]m = 3
- المخرجات
- 7
- الشرح
- هناك ثلاثة طلاب وثلاثة طرود، لذا يتم توزيع كل طرد ويكون الفرق
8 - 1 = 7.
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
افترض أنك تعرف بالفعل أصغر حزمة ستوزعها. ما الحزم الأخرى التي ينبغي أن توزّعها معها؟
بعد تثبيت أصغر حزمة، وزّع الحزم
m-1التي تليها مباشرةً في ترتيب الأحجام: فأي حزمة أكبر لا تؤدي إلا إلى زيادة الفجوة. في الترتيب المصعّد، تقع هذه الحزم متجاورةً بعضها إلى بعض.رتّب الحزم. كل مجموعة متتالية من
mجيرانًا تشكّل نافذة، ويكون فرقها هو قيمة آخر حزمة فيها ناقص قيمة أول حزمة. حرّك النافذة من اليسار إلى اليمين واحتفظ بأصغر فرق.
الحل
إن تجربة كل مجموعة من m الحزم بطيئة جدًا. أفضل اختيار دائمًا هو m حزم متجاورة بعد ترتيب الحزم. لذا رتّبها مرة واحدة، وستكون الإجابة أصغر فرق بين أي نافذة تضم m حزم متجاورة، ويمكن إيجاده في مرور واحد.
أصلح أصغر حزمة
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
ثبّت أصغر حزمة توزّعها، low. ولإبقاء أكبر حزمة صغيرة، خذ أصغر m-1 حزمة لا يقل حجمها عن low. عندئذٍ يكون الفرق هو حجم الحزمة رقم m الأصغر التي لا يقل حجمها عن low، ناقصًا low. جرّب كل حزمة بوصفها low، وتجاوز أيًّا منها إذا كان عدد الحزم التي لا يقل حجمها عنها أقل من m، واحتفظ بأصغر فرق.
كل اختيار من الاختيارات n يرشّح ما يصل إلى n حزمة ويرتّبها: O(n² log n). عندما يكون n = 10^4 حجمًا مختلفًا، فإن عمليات الترتيب وحدها تتطلب نحو 6 × 10^8 مقارنة.
الخوارزمية
- ابدأ
bestبقيمة لا يمكن لأي إجابة أن تتجاوزها. - لكل علبة
low، اجمع كل العلب التي تحتوي علىlowقطعة شوكولاتة على الأقل ورتّبها. - إذا كان عددها لا يقل عن
m، فإن الفرق بين العنصر الأصغر رقمmوlowيمثّل قيمة مرشحة. - احتفظ بأصغر قيمة مرشحة في
bestوأعِدها.
def minDifference(packets, m):
best = max(packets) - min(packets) # no gap can be wider than this
for low in packets:
# The packets that could go out alongside low, smallest first (low is one of them).
bigger = sorted(x for x in packets if x >= low)
if len(bigger) >= m:
best = min(best, bigger[m - 1] - low)
return bestرتّب وحرّك نافذة من m حزم
الفكرة
عند الترتيب تصاعديًا، تحتوي النافذة sizes[i..i+m-1] على أصغر حزمة أولًا وأكبر حزمة أخيرًا، لذا يكون الفرق sizes[i+m-1] - sizes[i].
يمكن دائمًا أن يكون الاختيار الأمثل نافذة. إذا تجاوز الاختيار حزمة تقع بين أصغر حزمة وأكبرها، فاستبدل بها أكبر حزمة. تبقى أصغر حزمة كما هي، ولا يمكن لأكبر حزمة إلا أن تصغر، لذا لا يزداد الفرق أبدًا. كرر ذلك حتى لا تبقى أي فجوة.
في المثال الأول، تعطي النوافذ المكوّنة من ثلاث حزم القيم 4 و5 و4 و6، لذا تكون الإجابة 4. يستغرق الترتيب O(n log n)، ويستغرق تمرير النافذة O(n).
الخوارزمية
- رتّب الحزم بترتيب تصاعدي في
sizes. - عيّن
bestإلىsizes[m-1] - sizes[0]، وهي النافذة الأولى. - لكل بداية
iمن 1 إلىn-m، قارنsizes[i+m-1] - sizes[i]معbestواحتفظ بالأصغر. - أعِد
best.
def minDifference(packets, m):
sizes = sorted(packets)
best = sizes[m - 1] - sizes[0]
# The window sizes[i..i+m-1] holds m packets; its first is the smallest, its last the largest.
for i in range(1, len(sizes) - m + 1):
best = min(best, sizes[i + m - 1] - sizes[i])
return best
أخطاء شائعة وحالات حدّية
- إنهاء النافذة عند
i+mبدلًا منi+m-1، ما يعني قياسm+1حزمة. - التوقف قبل النافذة الأخيرة. تبدأ القيم من 0 إلى
n-mشاملًا. بالنسبة إلى[1, 10, 20, 21]معm = 2، فإن استخدام حلقة بشرطi < n-mيفوّت الفرق الوحيد البالغ 1. - تخطي الترتيب. في
[9, 3, 15, 7, 11, 4]، يختلف أول ثلاث حزم بمقدار 12، بينما الإجابة هي 4. - قياس النافذة الأولى فقط. الحزم
mالأصغر هي أحد الخيارات، لكن أفضل مجموعة قد تبدأ من أي موضع. - ترتيب الأرقام كنصوص. في JavaScript، تضع
sort()من دون دالة مقارنة100000قبل9.
أسئلة شائعة3
ما هو التعقيد الزمني لمشكلة توزيع الشوكولاتة؟
يستغرق الفرز O(n log n)، ويستغرق تحريك نافذة من m حزم O(n)، لذا فإن الإجمالي هو O(n log n). المساحة الإضافية هي O(n) لنسخة مرتبة، أو O(1) بخلاف عملية الفرز نفسها إذا فرزت المُدخلات في مكانها.
هل تُعدّ مشكلة توزيع الشوكولاتة مسألة نافذة منزلقة؟
نعم، نافذة ذات حجم ثابت على الحزم المرتبة. بخلاف نافذة المجموع التراكمي، لا يوجد ما يجب تحديثه أثناء تحركها: فرق كل نافذة هو طرح حزمة بدايتها من حزمة نهايتها.
هل يمكن حلّ مسألة توزيع الشوكولاتة دون ترتيب؟
الأحجام هنا لا تتجاوز 10^5، لذا يرتبها فرز العد في زمن O(n + 10^5)، وينطبق الاستدلال نفسه. أما مع أحجام غير محدودة، فلا يمكن للمقارنات وحدها أن تتفوق على O(n log n): عندما تكون m = 2، تكون الإجابة 0 بالضبط عندما تتساوى حزمتان، ويتطلب اكتشاف عنصر مكرر هذا العدد من المقارنات في أسوأ الحالات.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def minDifference(packets, m):
# اكتب الشيفرة هنااختبار #1
اختبار #2
اختبار #3
الوسائط
packets = [9, 3, 15, 7, 11, 4] m = 3
الإخراج المتوقع
4