interesting-drink

Interesting Drink

يُباع مشروب في \(n\) متجرًا. سعر الزجاجة في المتجر رقم \(i\) هو \(x_i\) قطعة نقدية. خلال \(q\) يومًا تعرف أن فاسيلي يستطيع في اليوم رقم \(i\) أن ينفق \(m_i\) قطعة نقدية. لكل يوم، أوجد عدد المتاجر التي يستطيع فاسيلي أن يشتري منها زجاجة.

القيود:

\(1 \le n \le 10^5\)، \(1 \le x_i \le 10^5\)
\(1 \le q \le 10^5\)، \(1 \le m_i \le 10^9\)

الإدخال:

السطر الأول: عدد صحيح \(n\) — عدد المتاجر.
السطر الثاني: \(n\) عددًا \(x_1, x_2, \dots, x_n\) — الأسعار.
السطر الثالث: عدد صحيح \(q\) — عدد الأيام.
الأسطر الـ \(q\) التالية: عدد صحيح \(m_i\) في كل سطر.

المخرجات:

\(q\) سطرًا — لكل يوم، عدد المتاجر التي لا يزيد سعرها عن \(m_i\).

مثال:

الإدخال:

5
3 10 8 6 11
4
1
10
3
11

المخرجات:

الحل

فحص كل المتاجر في كل يوم يستغرق \(O(n \cdot q)\)، أي ما يصل إلى \(10^{10}\) عملية، وهذا بطيء جدًا.

بدلًا من ذلك نرتّب الأسعار مرة واحدة. في المصفوفة المرتّبة تشكّل الأسعار التي لا تزيد عن \(m\) بادئة من المصفوفة. إذا كان first هو موقع أول سعر أكبر من \(m\)، فإن البادئة تحتوي على first عنصرًا بالضبط، لذلك first هو الجواب. إذا لم يوجد مثل هذا السعر، فالجواب \(n\).

نجد first باستخدام البحث الثنائي من الدرس عن أول عنصر أكبر من أو يساوي \(X\)؛ التغيير الوحيد هو الشرط x[mid] > m.

يستغرق الترتيب \(O(n \log n)\) ويستغرق كل يوم \(O(\log n)\)، لذا يعمل الحل كله في زمن \(O((n + q) \log n)\).

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

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

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

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

    int q;
    cin >> q;

    for (int day = 0; day < q; day++) {
        int m;
        cin >> m;

        // find the first position with a price greater than m
        int left = 0, right = n - 1;
        int first = n;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (x[mid] > m) {
                first = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        cout << first << "\n";
    }
}