牛牛找工作

题目难度：三星
考察点：贪心、排序

方法1：暴力算法

1. 分析：
   对于每个小伙伴，从1-n遍历一遍找到超过自身能力值的情况下报酬最高的那个人，输出即可。
2. 复杂度分析：
   时间复杂度：O(m*n)
   空间复杂度：O(n)
3. 代码：

   #include <bits/stdc++.h>
   using namespace std;
   const int MAXN = 1e5+5;
   struct Node {
    int x, y;
   }a[MAXN];
   int main() {
    int n, m; cin>>n>>m;
    for(int i=0; i<n; i++) cin>>a[i].x>>a[i].y;
    while(m--) {
        int v; cin>>v;
        int ans = 0;
        for(int i=0; i<n; i++) if(v >= a[i].x) ans = max(ans, a[i].y);
        cout<<ans<<endl;
    }
    return 0;
   }

方法2：贪心+二分算法

1. 分析：
   我们首先按照工作的难度进行排序，然后创建一个mx数组，mx[i]表示前i个人所能获得的最大报酬，因为是按照难度进行排序，假设区间[l,r]中的难度是一样的为d，那么mx[r]一定是难度为d的所能获得的最大报酬。根据这个想法，我们可以对于难度进行二分，找到第一个难度大于d的下标id，然后输出mx[id-1]即可。
   tips:对于二分来说，我们可以运用upper_bound，来实现，还需要注意的是一定要在结构体中重载<，要不然无法进行排序。

2. 复杂度分析：
   时间复杂度：max{O(nlogn),O(m*logn)}
   空间复杂度：O(n)

3. 代码：

   #include <bits/stdc++.h>
   using namespace std;
   const int MAXN = 1e5+5;
   struct Node {
    int x, y;
    Node(){}
    Node(int a, int b):x(a),y(b) {}
    bool operator<(const Node m)const{ //重载<，对于排序来说是必须的。
        return x < m.x;
    }
   }a[MAXN];
   int mx[MAXN];
   int main() {
    int n, m; cin>>n>>m;
    for(int i=0; i<n; i++) cin>>a[i].x>>a[i].y;
    sort(a, a+n);
    mx[0] = a[0].y;
    for(int i=1; i<n; i++) mx[i] = max(mx[i-1], a[i].y);
    for(int i=0; i<m; i++) {
        int v; cin>>v;
        int id = upper_bound(a, a+n, Node(v, 0))-a;
        cout<<mx[id-1]<<endl;
    }
    return 0;
   }