Concert Tickets

題目

有 $n$ 張演唱會門票，每張票都有各自的價格，接著有 $m$ 位客人一個接一個的來。 每個客人都有自己願意付的價格，他們會買所有票裡面小於等於自己願付價格，且價格最高的那張票。

輸入

• 第一行有兩個正整數 $n$ 和 $m$ ，代表票的數量跟客人的數量。 $(1 \le n, m \le 2 \cdot 10^5)$
• 第二行有 $n$ 個整數 $h_i$，分別代表每張票的價格。$(1 \le h_i \le 10^9)$
• 第三行有 $m$ 個整數 $t_i$，分別代表每個客人的願付價格。$(1 \le t_i \le 10^9)$

輸出

每個客人分別會花多少錢買票，如果沒有可以買的票則輸出 $-1$。

範例測資

Input:
5 3
5 3 7 8 5
4 8 3

Output:
3
8
-1

第一位客人會買最接近且小於等於 $4$ 的票，也就是 $3$

第二位客人會買最接近且小於等於 $8$ 的票，也就是 $8$

第三位客人會買最接近且小於等於 $3$ 的票，但是唯一一張小於等於 $3$ 的票被第一位客人買走了，所以沒有符合第三位客人的票，因此輸出 $-1$

觀察

1. 將票價排序後不影響結果。
2. 針對每個查詢，可以買的票具有單調性。
3. 每次查詢過後，有機會得刪掉某個票價。

想法

每位客人都要找小於或等於某個價格的票，要怎麼最快找到符合條件的票呢 ? 二分搜是我們最好的選擇，因為排序後並不影響最終結果，並且票價具有單調性。最後的演算法是使用二分搜找到當前客人要買的票，並且將其從未售出的票裡面移除，因為移除不影響原序列單調性，下一位客人需要的票也可以直接使用二分搜找到答案。

為了確保陣列是排序的，並且能夠動態刪除元素，可以使用 C++ 內建的資料結構 multiset（因為票價可能重複，所以不能用 set）維護。

若你未曾使用過 multiset，請至 這裡 查看教學。

對於每個查詢，可以先使用 multiset 內建的 upper_bound 找到大於 $t_i$ 的最小票價，在使用 prev 找到他的前一個票價（也就是最大的，小於等於 $t_i$ 的票價）。

請注意，若 upper_bound 搜尋的結果正是最小的元素，就代表沒有可買的票。

最後，每次查詢的時間複雜度是 $\log(n)$，刪除元素的時間複雜度是 $\log(n)$，因此總時間複雜度是 $\log(n)$。

範例程式碼

C++ 範例

#include <bits/stdc++.h>
using namespace std;

int n, q, a;
multiset<int> ss;

int main(){

    // input
    cin >> n >> q;
    for (int i=0 ; i<n ; i++){
        cin >> a;
        ss.insert(a);
    }

    // queries
    for (int i=0 ; i<q ; i++){
        cin >> a;
        auto it = ss.upper_bound(a);

        if (it==ss.begin()){
            cout << -1 << "\n";
        }else{
            cout << *prev(it) << "\n";
            ss.erase(prev(it));
        }
    }

    return 0;
}

請注意，set/multiset 中，要使用 ss.lower_bound 的形式才能在 $\log (n)$ 的時間複雜度得到結果。