concert-tickets

Concert Tickets

CSES medium

توجد \(n\) تذكرة لحفل موسيقي، ولكل تذكرة سعر. ثم يصل \(m\) زبونًا واحدًا بعد الآخر.

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

القيود:

\(1 \le n, m \le 2 \cdot 10^5\)
\(1 \le h_i, t_i \le 10^9\)

الإدخال:

السطر الأول: عددان صحيحان \(n\) و \(m\).
السطر الثاني: \(n\) عددًا صحيحًا \(h_1, h_2, \ldots, h_n\) — أسعار التذاكر.
السطر الثالث: \(m\) عددًا صحيحًا \(t_1, t_2, \ldots, t_m\) — أعلى سعر لكل زبون، بترتيب وصولهم.

المخرجات:

لكل زبون، سطر فيه السعر الذي يدفعه، أو \(-1\) إذا لم يستطع الحصول على تذكرة.

مثال:

الإدخال:

5 3
5 3 7 8 5
4 8 3

المخرجات:

3
8
-1

الحل

نحتاج إلى بنية تبقي الأسعار المتبقية مرتبة، وتجد أكبر سعر \(\le t\)، وتحذف سعرًا واحدًا. البنية multiset تفعل الثلاثة في \(O(\log n)\). البنية set لا تكفي، لأن عدة تذاكر قد يكون لها السعر نفسه.

tickets.upper_bound(t) تُرجع أول سعر أكبر من \(t\).
إذا كان هذا هو العنصر الأول، فكل تذكرة سعرها أكبر من \(t\)، والجواب \(-1\).
وإلا فالعنصر الذي قبله مباشرة هو أكبر سعر \(\le t\).

نحذف التذكرة المبيعة بـ erase(it) باستعمال المكرِّر. أما erase(value) فتحذف كل التذاكر التي لها هذا السعر.

التعقيد الزمني \(O((n + m) \log n)\).

#include <iostream>
#include <set>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    multiset<int> tickets;
    for (int i = 0; i < n; i++) {
        int h;
        cin >> h;
        tickets.insert(h);
    }

    for (int i = 0; i < m; i++) {
        int t;
        cin >> t;

        // the first ticket with price greater than t
        auto it = tickets.upper_bound(t);
        if (it == tickets.begin()) {
            cout << -1 << "\n";  // every ticket is too expensive
        } else {
            it--;  // the most expensive ticket with price at most t
            cout << *it << "\n";
            tickets.erase(it);  // erase only this one ticket
        }
    }
}