CSES 2. Concert Tickets (1091)

출처: https://cses.fi/problemset/task/1091

---

문제 설명

There are n concert tickets available, each with a certain price. Then, m customers arrive, one after another.

Each customer announces the maximum price he or she is willing to pay for a ticket, and after this, they will get a ticket with the nearest possible price such that it does not exceed the maximum price.

입력

The first input line contains integers n and m: the number of tickets and the number of customers.

The next line contains n integers h_1,h_2,…,h_n: the price of each ticket.

The last line contains mm integers t_1,t_2,…,t_m: the maximum price for each customer.

출력

Print, for each customer, the price that they will pay for their ticket. After this, the ticket cannot be purchased again.

입력 예

5 3
5 3 7 8 5
4 8 3

If a customer cannot get any ticket, print −1.

출력 예

3
8
-1

제약조건

• 1 <= n,m <= 2x10^5
• 1 <= h_i, t_i <= 10^9

---

문제 풀이 

티켓 가격을 multiset에 저장하고, 희망 가격으로 lower_bound를 찾는다.

그 가격보다 낮은 가격이 있으면 출력하고, 없으면 -1을 출력한다.

프로그램 내용

...
    multiset <long, greater<long>> tPrice;

    for (int in=0; in < nTicket; ++in)
        cin >> temp;
        tPrice.insert(temp);

    for (int id = 0; id < nCustomer; ++id)
        cin >> temp;
        auto low = tPrice.lower_bound(temp);
        if ( low == tPrice.end())
            cout << -1 << endl;
        else
            cout << *low << endl;
            tPrice.erase(low);
...

 

Sorting and Searching ( link )