Concert Tickets

用python容易超時，不超時的話要用外部額外排序list套件，但要用到外部套件就不是個好選擇了，所以這裡提供用python表示想法，會用C++來實作

想法

仔細想想就會發現這題比較沒辦法用雙指針(因為涉及刪除)。

所以這裡的想法是

” 將顧客的預算插入到票價list中，取左邊那個 “

這樣就能取到<=票價的最優價格了

import bisect

n, m = map(int, input().split())
s = sorted(list(map(int, input().split())))
customers = list(map(int, input().split()))

for c in customers:
    i = bisect.bisect_right(s,c)
    if i == 0:
        print(-1)
    else:
        print(s[i - 1])
        s.pop(i - 1)

bisect.bisect_right(s,t)

會回傳” c要插入s裡的最佳index “

s = [1,2,3,4,5]
print( bisect.bisect_right(s,6)) # output 5

所以透過套件快速二分搜來達到快速找到該值右邊index

C++

透過multiset的upper_bound 來達到同樣效果，且multiset可以依值保持有序

#include <bits/stdc++.h>
#define io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;

int i;
vector<int> ans, li;
unordered_set<int> st;

int main(){ io;
    multiset<int> tik;
    int n,m,p;

    cin >> n>>m;
    for (i=0;i<n;i++){
        cin >> p;
        tik.insert(p);
    }

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

        auto it = tik.upper_bound(cus);

        if (it == tik.begin()) cout << -1 << endl;
        else{
            --it;
            cout << *it << "\n";
            tik.erase(it);


        }
    }
}