2018 网易 iOS [编程题] 牛牛选工作（80%通过率 -> 100%）

[TOC]

Question

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

输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数，分别表示工作的数量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

---

输出例子1:
100 
1000 
1001

Code(80%,超时）

这道题首先的解法就是暴力解法，以复杂度 O(MN) 的两重循环解决，而陷阱就在这里，因为限时2s，所以暴力解法只能解决范例，达到 10%。
所以会想到给杂乱的输入排个序，但是为了保护输出的顺序，所以不能给 A[M] 排序。所以按收入给工作排序，然后找到最大的工作，结束循环。这样也有问题，因为在最差情况下，复杂度还是 O(MN) ，所以最后通过率也只有80%。

/*
 网易 iOS 编程题-找工作
 
 这道题里设置的数值上限为 1000000000
 注意 int 值的 范围为  -2147483648～2147483647
 */

#include <iostream>
#include <algorithm>


typedef struct Job{
    int dif;
    int pay;
}Job;

bool compare(Job a,Job b)
{
    return a.pay > b.pay;   //降序排列，如果改为return a < b，则为升序
}

using namespace std;
int main(int argc, char *argv[]) {
    int N, M;       // N 为工作数量，M 为小伙伴数量
    
    
    cin >> N >> M;
    
    Job Jobs[N];    // N < 100000
    int A[M];       // M < 100000
    
    for (int i = 0; i < N; i++) {
        
        cin >> Jobs[i].dif >> Jobs[i].pay;
    }
    
    for (int i = 0; i < M; i++) {
        cin >> A[i];
    }
    
    sort(Jobs, Jobs+N, compare);
    
    for (int i = 0; i < M; i++) {
        int max = 0;
        for (int j = 0; j < N; j++) {
            if (A[i] >= Jobs[j].dif && max < Jobs[j].pay) {
                max = Jobs[j].pay;
                break;
            }
        }
        cout << max << endl;
        max = 0;
    }
    
}

Code (100%)

在这里我们换了一个思路，先将 A 数组复制出来，然后就不怕排序影响输出了。然后就是想办法控制住循环不要嵌套，使复杂度在 O(N) 。这里用到了 c++ 中的 map，具体使用类似于字典，在遍历一遍的情况下，对 A[i] 设置好了相应的报酬值。然后回到之前复制好的顺序输出即可。

/*
 网易 iOS 编程题-找工作
 
 这道题里设置的数值上限为 1000000000
 注意 int 值的 范围为  -2147483648～2147483647
 */

#include <iostream>
#include <algorithm>
#include <map>
#include <cstring>

typedef struct Job{
    int dif;
    int pay;
}Job;

bool compare(Job a,Job b)
{
    return a.dif > b.dif;   //降序排列，如果改为return a<b，则为升序
}

using namespace std;
int main(int argc, char *argv[]) {
    int N, M;       // N 为工作数量，M 为小伙伴数量
    map <int, int> topPay;
    
    cin >> N >> M;
    
    Job Jobs[N];    // N < 100000
    int A[M], B[M];     // M < 100000
    
    for (int i = 0; i < N; i++) {
        
        cin >> Jobs[i].dif >> Jobs[i].pay;
    }
    
    for (int i = 0; i < M; i++) {
        cin >> A[i];
    }
    
    sort(Jobs, Jobs+N, compare);
    for (int i = N-2; i >=0; i--) {
        Jobs[i].pay = Jobs[i].pay > Jobs[i+1].pay ? Jobs[i].pay:Jobs[i+1].pay;
    }
    
    memcpy(B,A,sizeof(A));
    sort(A, A+M);   // 默认升序
    
    int j = M-1;
    for (int i = 0; i < N; i++) {
        if (Jobs[i].dif <= A[j] && j >= 0) {
            topPay[A[j]] = Jobs[i].pay;
            --j;
            --i;
        }
    }
    
    for (int i = 0; i < M; i++) {

        cout << topPay[B[i]] << endl;

    }
    
}