（java实现）

题目描述：

为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了，于是他只好把这个任务交给了你。

输入描述：

每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数，分别表示工作的数量N(N<=100000)和小伙伴的数量M(M<=100000)。
接下来的N行每行包含两个正整数，分别表示该项工作的难度Di(Di<=1000000000)和报酬Pi(Pi<=1000000000)。
接下来的一行包含M个正整数，分别表示M个小伙伴的能力值Ai(Ai<=1000000000)。
保证不存在两项工作的报酬相同。

输出描述：

对于每个小伙伴，在单独的一行输出一个正整数表示他能得到的最高报酬。一个工作可以被多个人选择。

示例1：

输入

3 3
1 100
10 1000
1000000000 1001
9 10 1000000000

输出

100
1000
1001

问题分析：

核心是用HashMap来记录难度和不超过该难度的最大报酬。
先把工作的难度和报酬映射到HashMap
把人的能力也全部读进来，放到HashMap，报酬可以先设为0.
最后按难度从小到大（所以需要先排序）更新HashMap,key为难度，value为不超过难度的最大报酬。

work 和 worker 可以作为结构体节点：
work按照工作难度（di）从小到大排序，如果遇到相同的难度则按照薪资（pi）从大到小排序；
worker按照学生的能力从小到大排序，同时给worker增加id标识，以便后期正确输出；
为每个worker寻找符合其工作能力的最大薪资工作，因为工作和worker是排序好的，
所以下一个worke的能力一定是大于上一个worker的能力，下一个工作的要求也是要高于上一个工作的要求，所以在计算下一个学生的时候，
只需在上一个基础上继续进行，要么其和上一个worker相同，要么会得到要求更高，薪资更高的工作。

相关知识：

参考代码：

思路一实现：

import java.util.*;
public class Main {

    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        while (input.hasNext())
        {
            int n = input.nextInt();
            int m = input.nextInt();
            //输入工作能力和报酬
            //ArraysList<Work> work = new ArraysList<Work>();
            List<Work> work = new ArrayList<Work>();
            for (int i=0; i<n; i++)
            {
                work.add(new Work(input.nextInt(), input.nextInt()));
            }
            //Collection.sort(work,new MyComparator());
            Collections.sort(work,new MyComparator());
            //输入工人能力
            List<Work> worker = new ArrayList<Work>();
            for (int i=0; i<m; i++)
            {
                worker.add(new Work(input.nextInt(), i));
            }
            Collections.sort(worker, new MyComparator());
            int[] res = new int[m];
            int count = 0, max = 0;
            for (int i=0; i<m; i++)
            {
                while (count<n && worker.get(i).id>=work.get(count).id)
                {
                    max = Math.max(max, work.get(count).pay);
                    count++;
                }
                res[worker.get(i).pay] = max;
            }
            for (int i=0; i<m; i++)
                System.out.println(res[i]);
        }
    }
}

class Work
{
    int id;
    int pay;
    public Work(int id, int pay)
    {
        this.id = id;
        this.pay = pay;
    }
}

class MyComparator implements Comparator<Work>
{
    public int compare(Work w1,Work w2)
    {
        return w1.id-w2.id;  //升序
    }
}