演唱会门票，排序和搜索问题

Question

有n张音乐会门票，每张都有一定价格。然后，m个客户接连到达。每个客户都宣布他或她愿意支付的最高票价，然后，他们将获得价格尽可能接近的最高票价，以使票价不超过最高票价。

输入

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

The next line contains n integers h1,h2,…,hn: the price of each ticket.

The last line contains m integers t1,t2,…,tm: 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.

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

约束

 1 ≤ n, m ≤ 2⋅10^5

 1 ≤ hi, ti ≤ 10^9

示例

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

Output:
3
8
-1

我的方法是对所有h1，h2，... hn进行排序然后对每个ti使用二进制搜索，并将选定的h标记为inf。这将大致在nlog（n）+ mlog（n）中完成。有更好的主意吗？

我将代码实施为：

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<ll> v(n);
    ll p;
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < m; i++)
    {
        cin >> p;
        if (p < v.front())
            cout << -1 << "\n";
        else
        {   if(p>v.back()){
            cout<<v.back()<<"\n";
            v.pop_back();
        }else{
            auto it = upper_bound(v.begin(), v.end(), p);
            cout << *(it-1) << "\n";
            v.erase(it - 1);
        }
        }
    }
}

它在限定时间内没有执行。

Answer 1

这可以使用tree map之类的数据结构来解决。

对于票的每个固定价格，即tree map将它们放在树图中，以计数为价值。树状图可确保插入的键顺序正确。因此，例如，对于有问题的输入，地图将如下所示：]]

h[i]
然后在此地图中，使用对树地图的键集进行二进制搜索来搜索用户的出价。

在Java的树图中，您可以使用

3 -> 1
5 -> 2
7 -> 1
8 -> 1

方法获得地图中最大的键小于或等于您要查找的键

。此方法的时间复杂度为floorKey，因为Java中的树图使用Red Black Tree实现。

找到密钥后，将其值减小1，如果其值为0，则删除密钥。

使用每个用户的出价进行此操作。总时间复杂度为floorKey。

Java代码将（（未经测试）：

O(log(n))