牛牛找工作

题目描述：

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

思路：（自己测试几个都可以，但是官网测试不通过，不知道问题出在哪里？？）
工作数量为N，人数为M。先将工作排好序(O(NlogN))，再计算当前工作及小于它难度的工作的最大报酬(O(N))，放在maxPays数组。每次对于一个人，用二分查找找到适合的工作(MlogN)，然后从maxPays再取出最大的报酬即可。时间复杂度为O((N+M)logN)

public class FindBestWork {
    private static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int NumOfJobs=0;
        int NumOfPersons=0;

        if(sc.hasNextLine()){
            Integer[] twoNums = getIntegers(2);
            NumOfJobs = twoNums[0];
            NumOfPersons = twoNums[1];
        }

        if(NumOfJobs<=0||NumOfPersons<=0){
            return;
        }

        Job[] Jobs = new Job[NumOfJobs];
        for (int i = 0; i < NumOfJobs; i++) {
            Integer[] twoNums = getIntegers(2);
            Jobs[i] = new Job(twoNums[0], twoNums[1]);
        }

        Integer[] Abilities = getIntegers(NumOfPersons);

        Arrays.sort(Jobs, Comparator.comparing(a->a.getDifficulty()));
        Integer[] maxPays = new Integer[NumOfJobs];

        int maxPaySoFar = Jobs[0].getPay();
        for (int i = 0; i < NumOfJobs; i++) {
            if(Jobs[i].getPay()>maxPaySoFar){
                maxPaySoFar = Jobs[i].getPay();
            }

            maxPays[i] = maxPaySoFar;
        }

        for (Integer ability : Abilities) {
            int i = Arrays.binarySearch(Jobs, ability);
            if(i==-1){
                System.out.println("error!");
                break;
            }else if(i<-NumOfJobs){
                System.out.println(maxPays[NumOfJobs-1]);
            }else if(i>=0){
                System.out.println(maxPays[i]);
            }else{
                System.out.println(maxPays[(-i) - 2]);
            }
        }
    }

    private static class Job implements Comparable<Integer>{
        int Difficulty;
        int Pay;

        public Job(int difficulty, int pay) {
            Difficulty = difficulty;
            Pay = pay;
        }

        public int getDifficulty() {
            return Difficulty;
        }

        public void setDifficulty(int difficulty) {
            Difficulty = difficulty;
        }

        public int getPay() {
            return Pay;
        }

        public void setPay(int pay) {
            Pay = pay;
        }

        @Override
        public String toString() {
            return "Job{" +
                    "Difficulty=" + Difficulty +
                    ", Pay=" + Pay +
                    '}';
        }

        @Override
        public int compareTo(Integer ability) {
            if(this.getDifficulty()>ability)
                return 1;
            else if(this.getDifficulty()==ability)
                return 0;
            else
                return -1;
        }
    }

    private static Integer[] getIntegers(int nums){
        String line = sc.nextLine();
        // 使用一个或者多个空格
        String[] splits = line.split("\\s+");
        Integer[] Integers = new Integer[nums];
        for (int i = 0; i < nums; i++) {
            Integers[i] = Integer.valueOf(splits[i]);
        }
        return Integers;
    }
}

牛客网java第一名思路：
亮点是用了TreeMap来存放job和powers（value设置为0，方便后面取最大值的时候以job为准），同时比我自己的思路少了maxPays，直接用job的数据结构来存放，减少了内存的使用，但是时间复杂度差不多是一样的O((N+M)log(N+M))。

public class FindBestWork2 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        InputReader reader = new InputReader(System.in);
        PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));
        int jobnumber=reader.nextInt();
        int friendnumber=reader.nextInt();
        int[] powers=new int[friendnumber];
        TreeMap<Integer,Integer> jobs=new TreeMap<>();
        for(int i=0;i<jobnumber;i++) {
            int k=reader.nextInt();
            int v1=reader.nextInt();
            Integer v2=jobs.putIfAbsent(k, v1);
            if(v2!=null&&v1>v2) {
                jobs.put(k, v2);
            }
        }
        for(int i=0;i<friendnumber;i++) {
            powers[i]=reader.nextInt();
            jobs.putIfAbsent(powers[i], 0);
        }
        analyseJobs(jobs);
        for(int i:powers) {
            Integer s=jobs.get(i);
            writer.println(s);
        }
        writer.flush();
    }
    private static void analyseJobs(TreeMap<Integer, Integer> jobs) {
        Set<Map.Entry<Integer, Integer>> entries = jobs.entrySet();

        Map.Entry<Integer, Integer> c = null;
        for (Map.Entry<Integer, Integer> e : entries) {
            //因为为有序存储的，所以用小的key的value更新大的值的value
            if (c == null || c.getValue() < e.getValue()) {
                c = e;
            } else {
                e.setValue(c.getValue());
            }
        }
    }
    static class InputReader{
        private InputStream stream;
        private byte[] inbuf=new byte[1024];
        private int lenbuf=0;
        private int ptrbuf=0;

        public InputReader(InputStream stream) {
            this.stream=stream;
        }
        private int readByte() {
            if(lenbuf==-1) {
                throw new UnknownError();
            }
            if(ptrbuf>=lenbuf) {
                ptrbuf=0;
                try {
                    lenbuf=stream.read(inbuf);
                }catch(IOException e) {
                    throw new UnknownError();
                }
                if(lenbuf<=0) {
                    return -1;
                }
            }
            return inbuf[ptrbuf++];
        }
        public int nextInt() {
            int num=0,b;
            boolean minus=false;
            while((b=readByte())!=-1&&!((b>='0'&&b<='9')||b=='-'))
                ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = num * 10 + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }
    }

}