网易45：牛牛找工作

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

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;

/*
利用map容器来做。
1.创建map容器Job存储难度和薪酬，前者为key,后者为value.由于map默认是根据key自动升序排列的，所以就不用再特地写sort函数了
2.Job按照从小到大排列好后，输入员工能力，并将员工能力用Insert插入到Job中，能力为key,默认value为0.
  map用insert方法插入时不能插入已有关键字的数据。所以若有与Job中难度匹配的能力，其报酬不变。若没有与Job中难度匹配的能力，其报酬默认为0.
3.更新Job中能力与报酬的匹配情况，使得能力范围之内的报酬最大。
4.根据员工能力检索Job,输出对应报酬值
*/
int main()
{
    int N, M;
    map<int, int> Job;
    while (cin >> N >> M)
    {
        int a, b;
        //1.创建map容器Job存储难度和薪酬，前者为key,后者为value.
        for (int i = 0; i < N; i++)
        {
            cin >> a >> b;
            map<int, int>::iterator it = Job.find(a);
            //此处用"array方法"插入而不用Insert是因为若出现重复key前者会覆盖而后者不会
            //判断难度为a的是否已经插入了，若没有，直接插入，若出现了，比较大小，保留薪资大的那一个
            if (it == Job.end())
                Job[a] = b;
            //Job.insert(pair(int,int)(a,b));
            else
            {
                Job[a] = max(it->second, b);
            }
        }
        //2.Job按照从小到大排列好后，输入员工能力，并将员工能力用Insert插入到Job中，能力为key,默认value为0
        vector<int> ability(M);
        for (int i = 0; i < M; i++)
        {
            cin >> ability[i];
            //若对应难度已经存在在Job中，插入失败，若对应难度不存在，插入成功，且value置为0；
            Job.insert(pair<int, int>(ability[i], 0));
        }

        //3.更新Job中能力与报酬的匹配情况，使得能力范围之内的报酬最大。
        map<int, int>::iterator it = Job.begin();
        int maxP = 0;
        while (it!=Job.end())
        {
            if (it->second < maxP)
                it->second = maxP;
            else
                maxP = it->second;
            it++;
        }
        //4.根据员工能力检索Job,输出对应报酬值
        for (int i = 0; i < M; i++)
        {
            cout << Job[ability[i]] << endl;
        }
    }
    return 0;
}