牛牛找工作题解

在本题中，最先想到的是，将所有的能力值及对应的薪酬放到map中，然后每个循环对比，输出每个能力值所能获得的最大值，但是这样肯定超时，O（n*m）。

1. 将所有的能力值和薪酬一一对应填入map中，如果当前能力值有多个对应薪酬，只添加最高的那个。
2. 将同学的能力值也一一加入map中，如果原先已经有就直接跳过，如果没有就把value设为0。也同时记录下当前能力值，用于输出结果。
3. 遍历一遍map，由于map已经排过序，能力越大，对应的薪酬应该也越大，所以用快慢指针，将map中后面val小于前面val的值全部更新，使得map的val对应在当前能力值下所能获得最高的薪酬类似于动态规划。
   最后直接输出就可以了，直接对应存下的能力数组直接进行输出。

   #include<stdio.h>
   #include<vector>
   #include<iostream>
   #include<map>
   #include<math.h>
   using namespace std;
   int main(){
    int m,n;
    scanf("%d%d", &n,&m);
    map<int,int> mp;
    for(int i=0;i<n;i++){
        int diff,money;
        scanf("%d %d",&diff,&money);
        if(mp[diff] < money) mp[diff] = money;
    }
    vector<int> peopability(m);
    for(int i=0;i<m;i++){
        scanf("%d",&peopability[i]);
        mp.insert(make_pair(peopability[i],0));
    }
    auto pre = mp.begin();
    auto cur = mp.begin();
    cur++;
    while(cur != mp.end()){
        if(cur->second < pre->second){
            cur->second = pre->second;
        }
        cur++;
        pre++;
    }
    for(int i=0;i<m;i++){
        cout<<mp[peopability[i]]<<endl;
    }
   }