CSES – Concert Tickets

題目連結

題意

有 n 個門票跟 m 個顧客。第 i 張票的價錢用 h[i] 表示。第 j 個顧客最高只願意花 t[j] 塊錢買票 (只要 <= t[j] 第 j 個人都願意買)。一張票售出之後就不能再被買了。對於每個顧客，輸出他們買票花的價錢，如果不會買到票，輸出 -1。

解題方法

利用 multiset 內建的 upper_bound () ，並把 iterator 往前移一個就是第一個 <= t[j] 的票價。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
    multiset <int> s;
    for(int i = 0;i < n;i++){
        int x;
        cin >> x;
        s.insert(x);
    }
    for(int i = 0;i < m;i++){
        int x;
        cin >> x;
        auto it = s.upper_bound(x);
        if(it == s.begin()) {
            cout << "-1";
        } else {
            it--;
            cout << *it;
            s.erase(it);
        }
        cout << " \n"[i == n-1];
    }
}