Aggressive Cows

Q: ما هو التعقيد الزمني لمسألة وضع الأبقار العدوانية؟

يستغرق الترتيب O(n log n) ويستغرق البحث الثنائي O(n log D) ، حيث إن D هو امتداد الأكشاك مقسومًا على k-1 . وباستثناء نسخة مرتبة، تكون الذاكرة O(1) .

Q: لماذا تدخل البقرة الأولى دائمًا في الحظيرة الواقعة أقصى اليسار؟

اختر أي ترتيب صالح وانقل البقرة الواقعة في أقصى اليسار إلى الحظيرة الواقعة في أقصى اليسار. هذه البقرة لا تتحرك إلا مبتعدةً عن الأبقار الأخرى، لذا لا تتقلص أي مسافة، ويستخدم أحد أفضل الترتيبات الحظيرة الواقعة في أقصى اليسار.

Q: كيف تميّز البحث الثنائي عن الإجابة؟

يسأل السؤال عن أكبر أو أصغر قيمة يكون عندها شيء ما ممكنًا. والتحقق من قيمة واحدة أسهل بكثير من العثور على أفضل قيمة، كما أن الإجابات تنقلب مرة واحدة فقط مع ازدياد القيمة. هنا، القيمة هي الفجوة، والتحقق هو التوزيع الجشع.

متوسطالبحث الثنائي الترتيب الخوارزميات الجشعة

+10

يحتوي الحظيرة على حظائر مصطفّة على خط مستقيم واحد، ويمثل stalls[i] موقع الحظيرة رقم i. جميع المواقع مختلفة، ولا تأتي بترتيب محدد. عليك وضع k أبقار في k حظائر مختلفة، والأبقار تتشاجر عندما تقف متقاربة، لذا تريد أن تكون المسافة بين أقرب بقرتين أكبر ما يمكن.

أعِد أكبر قيمة ممكنة لأصغر مسافة بين أي بقرتين.

الدالة

aggressiveCows(stalls: integer-array, k: integer) → integer

stallsinteger-array: مواضع الأكشاك المتميزة، بأي ترتيب
kinteger: عدد الأبقار المراد وضعها
تُرجعinteger: أكبر مسافة ممكنة من بين أصغر المسافات بين بقرتين

القيود

2 ≤ stalls.length ≤ 5000
0 ≤ stalls[i] ≤ 10⁹
جميع المواضع في stalls متميزة.
2 ≤ k ≤ stalls.length

أمثلة

المدخلات: stalls = [10, 1, 7, 4, 15]k = 3
المخرجات: 6
الشرح: تقف الأبقار عند 1 و7 و15، وتفصل بينها مسافتان قدرهما 6 و8. لا ينجح الفاصل 7: فبعد 1 توضع البقرة التالية عند 10، ولا توجد حظيرة عند 17 أو أبعد.

سؤال إضافي

ما الذي يتغير إذا كانت الأكشاك مصطفّة على دائرة، بحيث يكون الكشك الأخير في الترتيب جارًا للكشك الأول أيضًا؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

اختر مسافةً واسأل: هل يمكن وضع k بقرة بحيث تكون المسافة بين كل بقرتين على الأقل تلك المسافة؟ تجيب عن ذلك عملية جشعة واحدة على الإسطبلات المرتبة. تتحول الإجابة من نعم إلى لا مرة واحدة مع ازدياد المسافة، لذا يجد البحث الثنائي آخر قيمة تكون الإجابة عندها نعم.

رتّب، ثم جرّب كل فجوة بالتتابع

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

رتّب المواقع. عندئذٍ تكون البقرتان الأقرب دائمًا متجاورتين، لذا تكون الفجوة g صالحة عندما تكون المسافة بين كل بقرتين متجاورتين g على الأقل.

لاختبار فجوة، ضع بقرة في الحظيرة الواقعة أقصى اليسار، ثم ضع بقرة في كل حظيرة تبعد g على الأقل عن آخر بقرة. يتيح هذا التوزيع الجشع وضع أكبر عدد ممكن من الأبقار مقارنةً بأي توزيع آخر. رتّب أي توزيع صالح بدءًا من اليسار: لن تكون البقرة i في التوزيع الجشع إلى يمين البقرة i في ذلك التوزيع أبدًا، لذا يعثر التوزيع الجشع على حظيرة لبقرته التالية في موعد لا يتأخر عن ذلك.

الفجوة 1 صالحة دائمًا، لذا جرّب g = 2, 3, ... وتوقّف عند أول فجوة تضع عددًا أقل من k من الأبقار. في المثال الأول، تضع الفجوة 6 ثلاث أبقار، بينما تضع الفجوة 7 بقرتين فقط، لذا تكون الإجابة 6.

مع بقرتين وحظيرتين عند 0 و10^9، فهذا يعني نحو 10^9 مرور على 5000 حظيرة، أي 5 × 10^12 خطوة.

الخوارزمية

رتّب المواقع.
اكتب اختبارًا للفجوة g: بقرة واحدة عند pos[0]، ثم بقرة عند كل حظيرة حيث pos[i] - last ≥ g، مع عدّ الأبقار.
ابدأ بـ gap = 1.
ما دام الاختبار للفجوة gap + 1 يضع ما لا يقل عن k من الأبقار، أضف 1 إلى gap.
أعِد gap.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    gap = 1  # positions are distinct, so a gap of 1 always fits every cow
    while cowsPlaced(pos, gap + 1) >= k:
        gap += 1
    return gap

البحث الثنائي عن الفجوة

الفكرة

أي توزيع تكون فيه كل فجوة لا تقل عن g+1 تكون فيه أيضًا كل فجوة لا تقل عن g، لذا تكون نتائج الفحوصات نعم، ...، نعم، لا، ...، لا. يعثر البحث الثنائي على آخر نتيجة نعم.

ابدأ البحث من lo = 1، وهي قيمة تنجح دائمًا، إلى hi = امتداد النطاق مقسومًا على k-1، مع التقريب إلى الأسفل: تترك k أبقار k-1 فجوات داخل النطاق، لذا لا يمكن أن تكون أصغر فجوة أكبر من ذلك. عند نجاح الفحص، عيّن lo = mid، لذا يجب تقريب mid إلى الأعلى؛ أما إذا قُرّب إلى الأسفل، فستتكرر lo = 5 وhi = 6 إلى الأبد.

في المثال الأول، امتداد النطاق هو 14 وk = 3، لذا hi = 7. تنجح الفجوة 4، وتنجح الفجوة 6، وتفشل الفجوة 7، وينتهي النطاق عند 6.

نطاق عرضه يصل إلى 10^9 ينتهي في نحو 30 فحصًا لـ5000 إسطبل، أي ما يقارب 150,000 خطوة.

الخوارزمية

رتّب المواقع.
اضبط lo = 1 وhi = (pos[n-1] - pos[0]) / (k-1)، مع التقريب إلى الأسفل.
ما دام lo < hi، احسب mid = lo + (hi - lo + 1) / 2.
إذا وضع الفحص الجشع عند mid ما لا يقل عن k من الأبقار، فاضبط lo = mid؛ وإلا فاضبط hi = mid - 1.
أعِد lo.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    lo = 1  # positions are distinct, so a gap of 1 always works
    hi = (pos[-1] - pos[0]) // (k - 1)  # k-1 gaps share the whole span
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # round up so lo = mid always moves
        if cowsPlaced(pos, mid) >= k:
            lo = mid  # mid fits, so the answer is mid or larger
        else:
            hi = mid - 1  # mid does not fit, so the answer is smaller
    return lo

أخطاء شائعة وحالات حدّية

تجاوز الفرز. في القائمة غير المرتبة [10, 1, 7, 4, 15] ومع فجوة مقدارها 6، يبدأ الفحص من 10، ولا يجد موقعًا لاحقًا يبعد عنه 6، فيُحصي بقرة واحدة.
تقريب mid إلى الأسفل بينما تُعيّن إحدى الدورات lo = mid. عندما يصبح hi = lo + 1، يتوقف النطاق عن التقلص ولا تنتهي الحلقة أبدًا.
التحقق من وجود k أبقار بالضبط. عند فجوة مقدارها 1، يضع المثال الأول 5 أبقار، أي أكثر من 3، ومع ذلك تكون الفجوة مناسبة؛ تحقّق من أن count ≥ k.
بدء عدد الأبقار من 0. تُحتسب البقرة في الموقع الأيسر، لذا يبدأ العدد من 1.

أسئلة شائعة3

ما هو التعقيد الزمني لمسألة وضع الأبقار العدوانية؟

يستغرق الترتيب O(n log n) ويستغرق البحث الثنائي O(n log D)، حيث إن D هو امتداد الأكشاك مقسومًا على k-1. وباستثناء نسخة مرتبة، تكون الذاكرة O(1).

لماذا تدخل البقرة الأولى دائمًا في الحظيرة الواقعة أقصى اليسار؟

اختر أي ترتيب صالح وانقل البقرة الواقعة في أقصى اليسار إلى الحظيرة الواقعة في أقصى اليسار. هذه البقرة لا تتحرك إلا مبتعدةً عن الأبقار الأخرى، لذا لا تتقلص أي مسافة، ويستخدم أحد أفضل الترتيبات الحظيرة الواقعة في أقصى اليسار.

كيف تميّز البحث الثنائي عن الإجابة؟

يسأل السؤال عن أكبر أو أصغر قيمة يكون عندها شيء ما ممكنًا. والتحقق من قيمة واحدة أسهل بكثير من العثور على أفضل قيمة، كما أن الإجابات تنقلب مرة واحدة فقط مع ازدياد القيمة. هنا، القيمة هي الفجوة، والتحقق هو التوزيع الجشع.

def aggressiveCows(stalls, k):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

الوسائط

stalls = [10, 1, 7, 4, 15]
k = 3

الإخراج المتوقع