Assign Cookies
لكل طفل i عامل جشع g[i]: أصغر حجم لقطعة البسكويت يجعله سعيدًا. ولكل قطعة بسكويت j حجم s[j]. يكون الطفل راضيًا عندما يحصل على قطعة بسكويت واحدة لا يقل حجمها عن عامل جشعه. يحصل كل طفل على قطعة بسكويت واحدة كحد أقصى، وتُعطى كل قطعة بسكويت لطفل واحد كحد أقصى. أعد أكبر عدد من الأطفال الذين يمكنك إرضاءهم.
الدالة
- ginteger-array
- عامل الجشع لكل طفل، أصغر حجم بسكويت يقبله
- sinteger-array
- حجم كل ملف تعريف ارتباط
- تُرجعinteger
- أكبر عدد من الأطفال الذين يمكن لكلٍّ منهم الحصول على بسكويتة بحجم لا يقل عن عامل الجشع الخاص به
القيود
1 ≤ g.length, s.length ≤ 50001 ≤ g[i], s[j] ≤ 105- قد يختلف طول المصفوفتين، ولا تكون أيٌّ منهما مرتبة.
أمثلة
- المدخلات
- g = [4, 2, 7]s = [3, 5, 1, 2]
- المخرجات
- 2
- الشرح
- بعد الترتيب، يريد الأطفال 2 و4 و7، وقطع البسكويت هي 1 و2 و3 و5. تُطعم قطعة البسكويت 2 الطفل الذي يريد 2، وتُطعم قطعة البسكويت 5 الطفل الذي يريد 4. لا يتبقى شيء يكفي الطفل الذي يريد 7، لذا الإجابة هي 2.
- المدخلات
- g = [3, 3, 3]s = [2, 2, 2]
- المخرجات
- 0
- الشرح
- يريد كل طفل كعكة بحجم 3 أو أكبر، وحجم كل كعكة هو 2، لذا لا يمكن إرضاء أي طفل.
+16 اختبارات مخفية عند الإرسال
سؤال إضافي
ماذا لو كان لكل طفل أيضًا أكبر حجم من البسكويت يقبله، بحيث لا تناسب قطعة البسكويت إلا نطاقًا معينًا؟ إلى أي طفل من الأطفال المنتظرين ينبغي أن نُعطي كل قطعة بسكويت حينها؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
أيّ طفلٍ يسهل إرضاؤه أكثر، وأيّ كعكة هي الأرخص التي لا تزال تُرضيه؟
لا يضر أبدًا إطعام الطفل بأصغر قطعة بسكويت تناسبه؛ إذ يمكنك الاحتفاظ بأي قطعة أكبر لتُطعم الأطفال أنفسهم الذين كان بإمكان تلك القطعة إطعامهم. لذا وزّع قطع البسكويت من الأصغر إلى الأكبر، وابدأ بإطعام الأطفال الأقل جشعًا.
رتّب المصفوفتين. مرّ على قطع البسكويت من الأصغر إلى الأكبر، واحتفظ بمؤشر يشير إلى أقلّ طفل جشع لا يزال ينتظر. إذا كانت قطعة البسكويت كبيرة بما يكفي لذلك الطفل، فسيشبع الطفل ويتقدّم المؤشر؛ وإلا، فهذه القطعة أصغر من أن تكفي أي طفل منتظر، لذا تخطّها. الموضع النهائي للمؤشر هو الإجابة.
الحل
السؤال هو: أي طفل يجب أن يحصل على أي كعكة؟ تجربة كل التوليفات تؤدي إلى عدد هائل من الاحتمالات، لكن قاعدة جشعة واحدة تحسم الأمر: ابدأ بإطعام أقل الأطفال جشعًا، وأعطهم أصغر كعكة تناسبهم. بعد ترتيب المصفوفتين، تتحول هذه القاعدة إلى مسح واحد باستخدام مؤشرين.
أصغر قطعة حلوى مناسبة لكل طفل
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
ابدأ بالأطفال من الأقل جشعًا إلى الأكثر جشعًا. ولكل طفل، افحص كل قطعة بسكويت لم تُستخدم بعد واختر أصغر قطعة تكفيه. إذا لم تناسبه أي قطعة، فسيبقى ذلك الطفل جائعًا. في المثال الأول، يريد الأطفال 2 و4 و7: يحصل الطفل الذي يريد 2 على قطعة البسكويت 2، ويحصل الطفل الذي يريد 4 على قطعة البسكويت 5، ولا يتبقى شيء للطفل الذي يريد 7.
لماذا نختار أصغر قطعة بسكويت مناسبة؟ يمكن لقطعة أكبر أن تُشبع كل طفل يمكن للقطعة الأصغر إشباعه، بل وأكثر. إن توزيع أصغر قطعة تكفي يُبقي القطع الأكبر للأطفال الأكثر جشعًا الذين يأتون لاحقًا، لذا لن تخسر أبدًا طفلًا كان بإمكانك إشباعه.
تكمن الكلفة في البحث. يفحص كل واحد من الأطفال n جميع قطع البسكويت وعددها m، لذا عندما يكون n = m = 5000، فسيكون هناك 25 مليون عملية تحقق، وهذا بطيء جدًا بالنسبة إلى أكبر الاختبارات.
الخوارزمية
- رتّب عوامل الجشع من الأصغر إلى الأكبر.
- احتفظ بعلامة لكل قطعة بسكويت تُبيّن ما إذا كانت مستخدمة.
- لكل طفل، افحص جميع قطع البسكويت وتذكّر أصغر قطعة غير مستخدمة يكون حجمها أكبر من أو يساوي جشع الطفل.
- إذا وجدت واحدة، فضع علامة على أنها مستخدمة واحتسب الطفل ضمن الأطفال الذين تم إرضاؤهم.
- أعِد العدد.
def findContentChildren(g, s):
used = [False] * len(s)
fed = 0
for need in sorted(g): # least greedy child first
best = -1
for j in range(len(s)):
if not used[j] and s[j] >= need and (best == -1 or s[j] < s[best]):
best = j
if best != -1:
used[best] = True
fed += 1
return fedرتّب كليهما واستخدم مؤشرين
الفكرة
يبحث المسح أعلاه، مرة تلو الأخرى، عن أصغر قطعة بسكويت تناسب الطفل. رتّب قطع البسكويت أيضًا، وعندها يختفي هذا البحث: تأتي قطع البسكويت بترتيب تصاعدي حسب الحجم، لذا تصادف أولًا أصغر قطعة بسكويت مناسبة.
مرّ على قطع البسكويت من الأصغر إلى الأكبر، واحتفظ بمؤشر واحد، child، يشير إلى أقل الأطفال جشعًا ممن لا يزالون ينتظرون. إذا كان حجم قطعة البسكويت أكبر من أو يساوي g[child]، فهذا يعني أن الطفل قد حصل على قطعة، ويتحرك المؤشر إلى الطفل التالي. أما إذا كانت أصغر، فهي أصغر من كل الأطفال الذين لا يزالون ينتظرون أيضًا، بما أنهم مرتّبون، لذا لا فائدة من قطعة البسكويت وتتابع المرور.
في المثال الأول، قطع البسكويت المرتّبة هي 1 و2 و3 و5، وقيم الجشع المرتّبة هي 2 و4 و7. قطعة البسكويت 1 أصغر من أن تناسب الطفل الذي يريد 2. قطعة البسكويت 2 تُطعم الطفل الذي يريد 2. قطعة البسكويت 3 أصغر من أن تناسب الطفل الذي يريد 4. قطعة البسكويت 5 تُطعم الطفل الذي يريد 4. يتوقف المؤشر عند 2، وهي الإجابة.
يتحرك كل مؤشر إلى الأمام فقط، لذا فإن المرور يستغرق O(n + m)، ويكون الفرز هو العامل الأكبر في الوقت. لا يحتاج الفرز في المكان إلى مصفوفات إضافية.
الخوارزمية
- رتّب
gوsبترتيب تصاعدي. - عيّن
child = 0، وهو الطفل الأقل طمعًا الذي لا يزال ينتظر. - لكل قطعة بسكويت، بدءًا من الأصغر: إذا كان
childلا يزال ضمنgوكانت قطعة البسكويت بحجمg[child]على الأقل، فأضف 1 إلىchild. - أعِد
child، وهو عدد الأطفال الذين أُطعموا.
def findContentChildren(g, s):
g.sort()
s.sort()
child = 0 # the least greedy child still waiting
for size in s: # smallest cookie first
if child < len(g) and size >= g[child]:
child += 1
return child
أخطاء شائعة وحالات حدّية
تنتج معظم الإجابات الخاطئة عن المطابقة بترتيب غير صحيح أو تحريك المؤشر الخطأ.
- إعطاء طفل كعكة أكبر مما يحتاج إليه. مع
g = [1, 2]وs = [1, 3]، فإن إعطاء الكعكة 3 للطفل الذي يريد 1 يترك الطفل الذي يريد 2 جائعًا، بينما تؤدي المطابقة الصحيحة إلى إطعام كليهما. - تحريك مؤشر الطفل عندما تكون الكعكة صغيرة جدًا. لا يزال الطفل بحاجة إلى كعكة؛ الكعكة هي التي لا تصلح.
- نسيان التحقق من الحد الأقصى لمؤشر الطفل. بعد إطعام جميع الأطفال، يجب ألا تؤدي الكعكات المتبقية إلى تجاوز نهاية
gعند القراءة. - المقارنة باستخدام
>بدلًا من≥. تكفي الكعكة التي يساوي حجمها عامل الجشع تمامًا. - ترتيب الأعداد كنصوص. في JavaScript، تضع
sort()من دون دالة مقارنة العدد 10 قبل 9.
أسئلة شائعة4
ما هو التعقيد الزمني لمسألة توزيع البسكويت؟
يستغرق فرز المصفوفتين O(n log n + m log m)، وتكون كلفة المرور بمؤشرين بعده O(n + m)، لذا فإن الفرز هو العامل المهيمن. يحافظ الفرز في المكان على المساحة الإضافية عند O(1)، باستثناء ما تستخدمه عملية الفرز نفسها.
لماذا ينجح الاختيار الجشع في مسألة توزيع ملفات تعريف الارتباط؟
ليكن k أصغر كعكة تناسب أقل طفل جشعًا. افترض أن توزيعًا أمثلًا يمنح ذلك الطفل كعكة أخرى. بدّل: يأخذ الطفل k، ومن كان لديه k يأخذ الكعكة الأخرى، التي لا يقل حجمها عن k، ولذلك يظل شبعانًا. لا يتغير العدد، لذا يمكن دائمًا أن يبدأ التوزيع الأمثل بالخيار الجشع، وتتكرر الحجة نفسها مع الأطفال والكعكات المتبقية.
هل يمكنك البدء بالطفل الأكثر جشعًا بدلًا من ذلك؟
نعم. رتّب المصفوفتين، ثم ابدأ من أكبر كعكة والطفل الأكثر جشعًا: إذا كانت أكبر كعكة متبقية تكفي الطفل الأكثر جشعًا المتبقي، فأطعمهما معًا وحرّك المؤشرين؛ وإلا فلن تكفي أي كعكة ذلك الطفل، لذا تخطَّ الطفل. ستحصل على العدد نفسه في الوقت نفسه.
هل تُعدّ مسألة إسناد ملفات تعريف الارتباط مسألة برمجة ديناميكية؟
لا. تُظهر حجة التبديل أن الاختيار الجشع آمن دائمًا، لذا يكفي الفرز ثم المرور مرة واحدة، بتعقيد O(n log n + m log m). ويعثر جدولٌ على المصفوفتين المرتبتين، يُملأ كما يُملأ جدول أطول تسلسل مشترك، على الإجابة أيضًا، لكنه يتطلب زمنًا بتعقيد O(n × m) للحصول على النتيجة نفسها.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def findContentChildren(g, s):
# اكتب الكود هناالحالة 1
الحالة 2
المدخلات
g = [4, 2, 7] s = [3, 5, 1, 2]
المتوقع
2