ferris-wheel

Ferris Wheel

CSES medium

يريد \(n\) طفلًا ركوب عجلة دوّارة. تتسع كل عربة لطفل واحد أو طفلين، ويجب ألا يزيد الوزن الكلي في العربة عن \(x\). وزن الطفل رقم \(i\) هو \(p_i\).

أوجد أقل عدد من العربات يكفي لكل الأطفال.

القيود:

\(1 \le n \le 2 \cdot 10^5\)
\(1 \le x \le 10^9\)
\(1 \le p_i \le x\)

الإدخال:

السطر الأول: عددان صحيحان \(n\) و \(x\) — عدد الأطفال وأكبر وزن مسموح في العربة.
السطر الثاني: \(n\) عددًا \(p_1, p_2, \dots, p_n\) — أوزان الأطفال.

المخرجات:

عدد صحيح واحد — أقل عدد من العربات.

مثال:

الإدخال:

4 10
7 2 3 9

المخرجات:

الحل

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

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

ننفّذ ذلك باستخدام مؤشرين على المصفوفة المرتّبة: left يشير إلى أخف طفل ليس له عربة، و right يشير إلى أثقل طفل ليس له عربة. كل خطوة تعطي عربة واحدة، وتحرّك right موقعًا واحدًا إلى اليسار، وتحرّك left موقعًا واحدًا إلى اليمين إذا ركب الطفلان معًا. تنتهي الحلقة عندما يتجاوز أحد المؤشرين الآخر.

يستغرق الترتيب \(O(n \log n)\) وتستغرق الحلقة \(O(n)\).

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, x;
    cin >> n >> x;

    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }

    sort(p.begin(), p.end());

    int left = 0;       // the lightest child without a gondola
    int right = n - 1;  // the heaviest child without a gondola
    int gondolas = 0;

    while (left <= right) {
        if (left < right && p[left] + p[right] <= x) {
            left++;  // the lightest child rides with the heaviest child
        }
        right--;
        gondolas++;
    }

    cout << gondolas << "\n";
}

نقاط يجب الانتباه لها

عندما يكون left == right يبقى طفل واحد فقط. الشرط left < right يمنعنا من جعل هذا الطفل شريكًا لنفسه.