Book Allocation Problem
يحتوي رفّ على كتب بترتيب ثابت، ويمثّل pages[i] عدد الصفحات في الكتاب i. وزّع الكتب على students طالبًا: يحصل كل طالب على مجموعة متصلة واحدة من الكتب المتجاورة، وعلى كتاب واحد على الأقل، ويُخصَّص كل كتاب لطالب واحد بالضبط. ويكون حمل الطالب هو إجمالي عدد الصفحات التي يحصل عليها.
أعِد أصغر قيمة ممكنة لأكبر حمل. إذا كان عدد الطلاب أكبر من عدد الكتب، فأعِد -1.
الدالة
- pagesinteger-array
- عدد صفحات كل كتاب، حسب ترتيبها على الرف
- studentsinteger
- عدد الطلاب الذين يتشاركون الكتب
- تُرجعinteger
- أصغر حمولة قصوى ممكنة، أو -1 عندما يكون عدد الطلاب أكبر من عدد الكتب
القيود
1 ≤ pages.length ≤ 50001 ≤ pages[i] ≤ 1051 ≤ students ≤ 104- أرجِع
-1عندماstudents > pages.length.
أمثلة
- المدخلات
- pages = [25, 40, 15, 30, 50]students = 3
- المخرجات
- 65
- الشرح
- وزّع
[25, 40]و[15, 30]و[50]: الأحمال 65 و45 و50. يفشل الحدّ 64: ينتج عن التوزيع[25]و[40, 15]و[30]و[50]، أي أربعة طلاب.
- المدخلات
- pages = [10, 20]students = 3
- المخرجات
- -1
- الشرح
- لا يمكن لكتابين أن يوفّرا لكل واحد من ثلاثة طلاب كتابًا واحدًا، لذا فالإجابة هي
-1.
- المدخلات
- pages = [7, 3, 9]students = 3
- المخرجات
- 9
- الشرح
- ثلاثة كتب وثلاثة طلاب، بحيث يحصل كل طالب على كتاب واحد. أثقلها هو الكتاب ذو 9 صفحات.
سؤال إضافي
أثبت أن متوسط الحصة، بعد تقريبه إلى الأعلى، مضافًا إليه الكتاب الأكثر سُمكًا، يشكّل دائمًا حدًا صالحًا. كم عدد عمليات التحقق التي يوفرها هذا الحد الأعلى عند ترتيب رف من الكتب الرقيقة؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
بدلًا من البحث عن أفضل عمليات القطع، حدّد حدًا أقصى للصفحات. كم عدد الطلاب الذين تحتاج إليهم إذا لم يُسمح لأيٍّ منهم بحمل أكثر من ذلك؟
وزّع الكتب حسب ترتيبها على الرف، وانتقل إلى الطالب التالي فقط عندما يتجاوز الكتاب التالي الحدّ. الحدّ الأعلى لا يتطلب عددًا أكبر من الطلاب أبدًا.
أعِد
-1عندما يكون عدد الطلاب أكبر من عدد الكتب. وإلا، فاستخدم البحث الثنائي لإيجاد الحد، بدءًا من الأكبر بين سُمك الكتاب الأكثر سُمكًا والحصة المتوسطة، وصولًا إلى المجموع الكلي.
الحل
هناك طرق كثيرة جدًا لتقسيم الرف، لكن اختبار حدّ صفحة واحد غير مكلف: وزّع الكتب حسب ترتيبها على الرف، وانتقل إلى الطالب التالي عندما تتجاوز الصفحة الحدّ، ثم احسب عدد الطلاب. لا يحتاج الحدّ الأعلى أبدًا إلى عدد أكبر من الطلاب، لذا تشكّل الحدود التي تنجح نطاقًا متصلًا، ويعثر البحث الثنائي على نقطة بدايته.
زِد حدّ الصفحات صفحةً واحدةً في كل مرة
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
ابدأ عند L = max(pages)، لأن شخصًا ما يحمل الكتاب الأكثر سُمكًا، وزِد L صفحةً واحدةً في كل مرة إلى أن يصبح العدد الناتج عن الخوارزمية الجشعة مناسبًا لعدد students. فشل كل حدٍّ أدنى أصغر، لذا فإن أول حدٍّ يناسب هو الإجابة. في المثال الأول، يتطلب كل حد من 50 إلى 64 أربعة طلاب، بينما يتطلب الحد 65 ثلاثة طلاب: أي 16 عملية تحقق.
قد تكون الإجابة هي الرف بأكمله: طالب واحد و5000 كتاب، يحتوي كل منها على 10^5 صفحة، يعني نحو 5 × 10^8 حدٍّ، وكل حد يتطلب المرور على 5000 كتاب. في عمود الزمن، تمثل A الإجابة، ويمثل m الكتاب الأكثر سُمكًا.
الخوارزمية
- إذا كان
students > pages.length، فأعِد-1. - اكتب العدد الجشع لحدّ
L: ابدأ بطالب واحد وحِمل قدره 0؛ عندما يكونload + pages[i] > L، أضف طالبًا واجعل الحملpages[i]، وإلا فأضف الكتاب إلى الحمل. - اجعل
Lمساويًا لأسمك كتاب. - ما دام العدد عند
Lأكبر منstudents، أضف 1 إلىL. - أعِد
L.
def studentsNeeded(pages, limit):
count, load = 1, 0 # the first student starts with no pages
for p in pages:
if load + p > limit:
count += 1 # this book opens the next student's block
load = p
else:
load += p
return count
def allocateBooks(pages, students):
if students > len(pages):
return -1 # someone would get no book
limit = max(pages) # the thickest book has to fit somewhere
while studentsNeeded(pages, limit) > students:
limit += 1
return limitالبحث الثنائي ضمن حدّ الصفحة
الفكرة
العدد الجشع هو أقل عدد من الطلاب يمكن أن يستخدمه أي تقسيم عند L. وعند المقارنة طالبًا بطالب مع أي تقسيم آخر، لا يتوقف كل طالب في التقسيم الجشع إلا عندما لا يتسع الكتاب التالي، لذا يصل إلى موضع لا يقل عن موضع الطالب المقابل على الرف. لا بأس إن كان لديك عدد أقل من الطلاب: يمكن لطالب يحمل كتابين أن يمرر أحدهما إلى طالب لا يحمل أي كتاب، من دون زيادة أي حمل.
لذا يكون L صالحًا بالضبط عندما يكون العدد الجشع أقل من أو يساوي students. وكل ما يكون صالحًا عند L يكون صالحًا عند L+1، لذا يعثر البحث الثنائي على أول حد صالح.
يبدأ النطاق بالأكبر من max(pages) ومتوسط الحصة، أي total / students مقربًا إلى الأعلى، لأن أثقل حمل لا يقل عن أي منهما. والحد الأعلى هو total. في المثال الأول، يتراوح النطاق من 54 إلى 160، ويجرّب البحث 107 و80 و67 و60 و64 و66 و65.
الخوارزمية
- إذا كان
students > pages.length، فأعِد-1. - اجمع
totalواعثر على الكتاب ذي أكبر عدد من الصفحات. عيّنloإلى الأكبر بين عدد صفحات هذا الكتاب و(total + students - 1) / students، وعيّنhi = total. - ما دام
lo < hi، احسبmid = lo + (hi - lo) / 2. - نفّذ حساب العدد بالطريقة الجشعة للقيمة
mid. إذا لم يتجاوز العددstudents، فعيّنhi = mid؛ وإلا فعيّنlo = mid + 1. - أعِد
lo.
def studentsNeeded(pages, limit):
count, load = 1, 0 # the first student starts with no pages
for p in pages:
if load + p > limit:
count += 1 # this book opens the next student's block
load = p
else:
load += p
return count
def allocateBooks(pages, students):
if students > len(pages):
return -1 # someone would get no book
total = sum(pages)
# no limit can be below the thickest book or below the average share
lo = max(max(pages), (total + students - 1) // students)
hi = total # one student could carry the whole shelf
while lo < hi:
mid = lo + (hi - lo) // 2
if studentsNeeded(pages, mid) <= students:
hi = mid # mid is enough, so the answer is mid or lower
else:
lo = mid + 1 # mid needs too many students
return lo
أخطاء شائعة وحالات حدّية
- تجاوز التحقق من
-1. بالنسبة إلى[10, 20]و3 طلاب، يكون العدد الجشع عند حدّ 20 هو 2، لذا يعيد البحث 20. - بدء النطاق بمتوسط الحصة وحده. بالنسبة إلى
[1, 9]وطالبين، يكون المتوسط 5، وعندها يضع النهج الجشع الكتاب ذا 9 صفحات وحده، ويحسب العدد 2، ويعيد 5. - التحقق من أن العدد يساوي
studentsتمامًا. بالنسبة إلى[5, 5, 5, 5, 5, 5]و4 طلاب، تكون الإجابة 10، ويكون العدد الجشع 3. - ترتيب الكتب. تعطي
[10, 1, 1, 10]مع طالبين الناتج 11، لكن بعد ترتيبها إلى[1, 1, 10, 10]تعطي الناتج 12.
أسئلة شائعة3
هل مشكلة Book Allocation Problem هي نفسها مشكلة Split Array Largest Sum؟
نعم. كلاهما يقسم مصفوفة إلى عدد ثابت من الكتل المتجاورة غير الفارغة، ويقلل أكبر مجموع للكتل، ويمكن حل كليهما بالبحث الثنائي نفسه مع التحقق الجشع نفسه. يضيف إصدار الكتاب حالة -1.
ما هو التعقيد الزمني لمسألة تخصيص الكتب؟
زمن O(n log S) ومساحة إضافية O(1)، حيث إن n هو عدد الكتب وS هو إجمالي عدد الصفحات. يتطلب كل حدّ تتم تجربته مرورًا واحدًا على الكتب، ويجرّب البحث نحو log2 S حدود: 29 على رفّ يحتوي على 5 × 10^8 صفحة.
متى يكون من المستحيل توزيع الكتب؟
فقط عندما يكون عدد الطلاب أكبر من عدد الكتب، إذ يحتاج كل طالب إلى كتاب واحد على الأقل. عندما يتوفر عدد كافٍ من الكتب، يمكن لأي مجموعة من كتابين أو أكثر أن تعطي كتابها الأخير لطالب لا يملك أي كتاب، إلى أن يحصل الجميع على كتاب واحد.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def allocateBooks(pages, students):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
pages = [25, 40, 15, 30, 50] students = 3
الإخراج المتوقع
65