【编程题】网易2019笔试：牛牛找工作

做了很多次笔试，编程题总是不能在规定时间内完成。一个原因是算法图的部分没有看。还有一个原因是题做得太少。今天开始打算有空的时候整理一下做过的编程题。总结一下知识点，也对自己的做题历程做一个记录。。。

题目

为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了，于是他只好把这个任务交给了你。
输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数，分别表示工作的数量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

解题思路

首先将工作难度和对应薪资储存在二维数组，按能力要求增序排序。
排序后需要更新每个难度下的薪资为可获得的最大值(因为可能存在能力要求高的工作薪资反而低的情况)。

用二分查找确定能胜任的最大工作难度及其最大报酬。

代码

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int N=scanner.nextInt();
        int M=scanner.nextInt();
        int[][] jobmap= new int[N][2];
        for(int i=0;i<N;i++){
            jobmap[i][0]=scanner.nextInt();
            jobmap[i][1]=scanner.nextInt();
        }
        //将 薪资-能力 二维数组按能力要求增序排序
        Arrays.sort(jobmap,(int[] o1, int[] o2) ->  o1[0]-o2[0]);
        //排序后需要更新每个ability下的薪资为 可获得的最大值(如果低能力要职位的求薪资高于高能力要求职位的薪资，则更新高能力要求职位的薪资为高薪资)
        for (int i = 0; i < jobmap.length - 1; i++) {
            if (jobmap[i][1] > jobmap[i + 1][1]) {
                jobmap[i + 1][1] = jobmap[i][1];
            }
        }
        int[] people = new int[M];
        for(int i=0;i<M;i++){
            people[i]=scanner.nextInt();
        }
        // 二分查找确定能胜任的最大工作难度及其最大报酬
        for (int i = 0; i < people.length; i++) {
            int index = Arrays.binarySearch(jobmap, new int[] {people[i], 0}, (int[] jd1, int[] jd2) ->jd1[0] - jd2[0]);
            index = index < 0 ? -(index + 1) - 1: index;
            System.out.println(index >= 0 ? jobmap[index][1] : 0);
        }
    }
}

总结

在初次编写代码的时候没有考虑到不一定报酬和工作难度都成正比。考虑不周全，需要注意。
在初次编写代码的时候，每个人都对所有工作进行遍历查找一次，时间复杂度为O(n²)。在数据量较大时性能不高，导致超时。改为二分查找后时间复杂度为O(log2(n))。
在使用Arrays.sort(T[] a, Comparator<? super T> c)方法时,使用了lambda表达式替代了匿名内部类。注意返回参数一减参数二的值是增序。
在使用Arrays.binarySearch(T[] a, T key, Comparator<? super T> c)时也使用了lambda表达式，在使用该方法前需要先使用sort方法排序。当查询的Key存在时，这个方法返回key在该数组中的下标，否则返回(-(insertion point) - 1)，insertion point指的是key在这个数组中应该插入的位置。也就是第一个比key大的值的下标，当key比所有值都大的时候，返回数组长度。所以当且仅当查找到key时，该方法的返回值才是正数。所以我们要寻找的最大报酬的工作的下标为 -(index + 1) - 1。

Java API中对Arrays.binarySearch(T[] a, T key, Comparator<? super T> c)返回值的描述

index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.