牛牛找工作

方法：
　　排序+双指针

想法：
　　工人们只能做难度小于等于他能力值的工作，将工作的难度按升序排序，遍历工作难度的同时记录最大收益，一定是当前工人能获得的最大收益。

算法：
　　由于不止一个工人，如果每个工人都按上述操作进行，时间复杂度是Ｏ（ｎ＊ｍ）的，不能通过此题。考虑将工人的能力值也按升序排序，不失一般性，worker[i]能做的工作，worker[i+1]也一定能做。
　　顺序遍历工人的同时，需要一个指针index指向最后一个难度<=当前工人能力值的工作、一个变量max_记录最大利润，随着遍历的进行拓展新的工作，更新max_;
　　排序使用的方式有很多种，可以使用map自动排序，将difficulty和profit放入结构体中统一排序等，这里使用下标排序。

复杂度分析：
　　时间复杂度：O(NlogN+MlogM)，其中 N 是工作个数，M 是工人数量,两次排序。
　　空间复杂度：O(max(N,M))，job_idx,worker_idx 的额外空间。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, m, index = 0, max_ = 0;
    scanf("%d %d", &n, &m);
    vector<int>difficulty(n), profit(n), worker(m);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &difficulty[i], &profit[i]);
    for (int i = 0; i < m; i++)
        scanf("%d", &worker[i]);
    vector<int>job_idx(n), worker_idx(m), ret(m);
    iota(job_idx.begin(), job_idx.end(), 0);
    sort(job_idx.begin(), job_idx.end(), [&](int& a, int& b) {return difficulty[a] < difficulty[b]; });
    iota(worker_idx.begin(), worker_idx.end(), 0);
    sort(worker_idx.begin(), worker_idx.end(), [&](int& a, int& b) {return worker[a] < worker[b]; });
    for (int i = 0; i < m; i++)
    {
        while (index < job_idx.size() && difficulty[job_idx[index]] <= worker[worker_idx[i]])
            max_ = max(max_, profit[job_idx[index++]]);
        ret[worker_idx[i]] = max_;
    }
    for (int i = 0; i < m; i++)
        printf("%d\n", ret[i]);
    return 0;
}