Car Fleet

Q: ما هو التعقيد الزمني لمشكلة أسطول السيارات؟

يستغرق الترتيب حسب الموضع O(n log n) ، وتستغرق عملية المرور باستخدام المكدس O(n) ، لذا يكون الإجمالي O(n log n) من حيث الزمن و O(n) من حيث الذاكرة. أما فحص كل سيارة مقارنةً بكل سيارة أمامها فيستغرق O(n²) .

Q: كيف تقارن أوقات الوصول دون استخدام الأعداد ذات الفاصلة العائمة؟

وقت الوصول هو dist / speed . بما أن السرعات موجبة، فإن d1 / s1 > d2 / s2 تتحقق بالضبط عندما d1 × s2 > d2 × s1 . كلا الطرفين عددان صحيحان لا يتجاوزان 10^12 ، لذا احسبهما باستخدام نوع ذي 64 بت، وتكون المقارنة دقيقة، من دون الحاجة إلى التعامل مع التقريب.

متوسطالمكدس الترتيب

+10

تسير السيارات على طريق ذي مسار واحد باتجاه الميل target. تبدأ السيارة i عند الميل position[i] وتسير بسرعة speed[i] ميلًا في الساعة. لا يمكن لأي سيارة تجاوز أخرى: فالسيارة التي تلحق بسيارة أبطأ منها تبقى خلفها مباشرة، ومنذ ذلك الحين تتحرك السيارتان معًا بسرعة السيارة الأبطأ، لتشكّلا أسطولًا.

وتُعد السيارة الواحدة أسطولًا أيضًا، كما أن السيارة التي تصل إلى أسطول عند الوجهة تمامًا تنضم إليه. أعد عدد الأساطيل التي تصل إلى الوجهة.

الدالة

carFleet(target: integer, position: integer-array, speed: integer-array) → integer

targetinteger: الميل الذي تتجه إليه كل سيارة
positioninteger-array: الميل الابتدائي لكل سيارة
speedinteger-array: سرعة كل سيارة، بالأميال في الساعة
تُرجعinteger: عدد الأساطيل التي تصل إلى الوجهة

القيود

n == position.length == speed.length
1 ≤ n ≤ 10⁴
1 ≤ target ≤ 10⁶
0 ≤ position[i] < target
1 ≤ speed[i] ≤ 10⁶
جميع المواضع مختلفة.

أمثلة

المدخلات: target = 20position = [14, 2, 8, 17, 0]speed = [3, 6, 4, 1, 2]
المخرجات: 2
الشرح: تحتاج السيارات الموجودة عند الأميال 17 و14 و8 و2، إذا سارت كل منها بمفردها، إلى 3 و2 و3 و3 ساعات، لذا تلحق السيارة عند الميل 14 بالسيارة عند الميل 17، وتصل السيارتان الأخريان إليهما عند الميل 20. تحتاج السيارة عند الميل 0 إلى 10 ساعات، وتصل بمفردها.

المدخلات: target = 9position = [0, 4, 7]speed = [1, 2, 3]
المخرجات: 3
الشرح: تحتاج السيارات عند الأميال 7 و4 و0 إلى 2/3 و5/2 و9 ساعات. وستصل كل سيارة بعد السيارة التي أمامها، لذا لن تلحق أي سيارة بأخرى: 3 مجموعات.

سؤال إضافي

المواضع أعداد صحيحة أصغر من target. هل يمكنك عدّ الأساطيل في زمن O(n + target)، دون استخدام فرز بالمقارنة؟

تلميحات

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

فُتح 0 من 3

الحل

في مسار واحد، لا يتغير ترتيب السيارات أبدًا، وما يحسم كل شيء هو موعد وصول كل سيارة لوحدها: (target - position[i]) / speed[i]. مرّ على السيارات بدءًا من الأقرب إلى الوجهة وانتهاءً بالأبعد. لا تبدأ السيارة أسطولًا جديدًا إلا إذا كان وصولها سيحدث بعد وصول الأسطول الذي أمامها بصرامة.

تحقّق من كل سيارة أمامك

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

الفكرة

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

تفحص كل سيارة السيارات الـn كلها: 10^8 عملية تحقق عندما تكون n = 10^4.

الخوارزمية

عيّن fleets = 0.
لكل سيارة i، انظر إلى كل سيارة j بحيث position[j] > position[i].
إذا وُجدت j تحقق (target - position[j]) × speed[i] ≥ (target - position[i]) × speed[j]، فهذا يعني أن السيارة i قد لَحِقَت بها سيارة: تخطَّها.
وإلا، تقود السيارة i مجموعةً من السيارات: أضف 1 إلى fleets.
أعِد fleets.

def carFleet(target, position, speed):
    n = len(position)
    fleets = 0
    for i in range(n):
        dist = target - position[i]
        caught = False
        for j in range(n):
            # Car j is ahead and would not arrive before car i: car i catches it.
            # (target - position[j]) / speed[j] >= dist / speed[i], without division.
            if position[j] > position[i] and (target - position[j]) * speed[i] >= dist * speed[j]:
                caught = True
                break
        if not caught:
            fleets += 1
    return fleets

رتّب حسب الموقع واجعل الأساطيل متراصّة

الفكرة

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

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

في المثال 1، ترتيب السيارات هو عند المواقع 17 و14 و8 و2 و0، ونسبة المسافة إلى السرعة هي 3/1, 6/3, 12/4, 18/6, 20/2. أضف (3, 1). تنضم السيارة عند الموقع 14، لأن 6 × 1 > 3 × 3 غير صحيحة. تتعادل السيارة عند الموقع 8، إذ إن 12 × 1 = 3 × 4، وتنضم، وكذلك السيارة عند الموقع 2. أما السيارة عند الموقع 0، فإن 20 × 1 > 3 × 2: أضفها.

الخوارزمية

رتّب فهارس السيارات حسب الموقع، من الأكبر إلى الأصغر.
ابدأ بمكدس فارغ من الأساطيل.
لكل سيارة، احسب dist = target - position[i].
إذا كان المكدس فارغًا أو dist × topSpeed > topDist × speed[i]، فأضف (dist, speed[i]) إلى المكدس؛ وإلا تنضم السيارة إلى الأسطول الموجود في أعلى المكدس.
أعِد حجم المكدس.

def carFleet(target, position, speed):
    # Visit the cars from the one closest to the target backward.
    order = sorted(range(len(position)), key=lambda i: position[i], reverse=True)
    # One entry per fleet: (distance, speed) of the car at its front, which sets its arrival time.
    stack = []
    for i in order:
        dist, spd = target - position[i], speed[i]
        # dist / spd > top_dist / top_spd, compared without division:
        # this car arrives after the fleet ahead, so it never catches it.
        if not stack or dist * stack[-1][1] > stack[-1][0] * spd:
            stack.append((dist, spd))
    return len(stack)

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

احتساب التعادل التام أسطولًا جديدًا. تنضم السيارتان عند الميلين 8 و2 في المثال 1 إلى الأسطول عند الميل 20. أضِف فقط عندما يكون الوقت متأخرًا تمامًا.
تجاوز السعة في الضرب التبادلي. 10^6 × 10^6 = 10^12 لا يتسع في 32 بتًا: في Java وC وC++ وC# وRust، استخدم نوعًا بعرض 64 بتًا قبل الضرب؛ وفي R، استخدم الأعداد العشرية.
الترتيب بالاتجاه الخاطئ. البدء بالسيارة الأبعد عن الوجهة يعني مقارنة كل سيارة بالسيارات التي خلفها، والتي لا يمكنها أبدًا إعاقة حركتها.
ترتيب position وحده. رتّب الفهارس أو أزواج (الموضع، السرعة)، كي تبقى كل سرعة مرتبطة بسيارتها.

أسئلة شائعة3

ما هو التعقيد الزمني لمشكلة أسطول السيارات؟

يستغرق الترتيب حسب الموضع O(n log n)، وتستغرق عملية المرور باستخدام المكدس O(n)، لذا يكون الإجمالي O(n log n) من حيث الزمن وO(n) من حيث الذاكرة. أما فحص كل سيارة مقارنةً بكل سيارة أمامها فيستغرق O(n²).

لماذا يستخدم Car Fleet مكدسًا؟

عند استعراض السيارات من الأمام، لا يلزم مقارنة كل سيارة جديدة إلا بالأسطول الذي أمامها مباشرة، أي الأسطول الذي تكوّن أخيرًا. وتُبقي المكدّسة ذلك الأسطول في القمة. وبما أن ما يُقرأ هو العنصر الموجود في القمة فقط، فيمكن استخدام متغيرين أيضًا؛ كما تتيح لك المكدّسة الاحتفاظ بالأساطيل نفسها.

كيف تقارن أوقات الوصول دون استخدام الأعداد ذات الفاصلة العائمة؟

وقت الوصول هو dist / speed. بما أن السرعات موجبة، فإن d1 / s1 > d2 / s2 تتحقق بالضبط عندما d1 × s2 > d2 × s1. كلا الطرفين عددان صحيحان لا يتجاوزان 10^12، لذا احسبهما باستخدام نوع ذي 64 بت، وتكون المقارنة دقيقة، من دون الحاجة إلى التعامل مع التقريب.

def carFleet(target, position, speed):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

الوسائط

target = 20
position = [14, 2, 8, 17, 0]
speed = [3, 6, 4, 1, 2]

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