牛客网2019真题-1-牛牛找工作

1. 牛牛找工作

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

1.遍历：o(M*N),超时
2.排序+map:
本题中，工作可以多次选择，只需要考虑工作，建立一个map,存储工作能力-报酬映射关系，把小伙伴的能力和报酬也存储进去，报酬初始化为0；从小到大依次更新最大报酬，有动态规划和马尔可夫过程的思想存在，当前最大报酬取决于当前能力与前一个能力对应的最大报酬。

import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        //D为工作难度，P为报酬，A为小伙伴的能力值
        int[] D = new int[N], P = new int[N], A = new int[M];
        Map<Integer, Integer> map = new TreeMap<>();
        for(int i = 0; i < N; i++){
            D[i] = sc.nextInt();
            P[i] = sc.nextInt();
            if(!map.containsKey(D[i])){
                map.put(D[i], P[i]);
            }else{
                if(P[i] > map.get(D[i])){
                    map.put(D[i], P[i]);//工作难度相同
                }
            }
        }
        //小伙伴的能力,并且插入到map中
        for(int i = 0; i < M; i++){
            A[i] = sc.nextInt();
            if(!map.containsKey(A[i])){
                map.put(A[i], 0);
            }
        }
        //更新map的value值
        int max = Integer.MIN_VALUE;
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            max = Math.max(max, entry.getValue());
            map.put(entry.getKey(), max);
        }
        for(int i = 0; i < A.length; i++){
            System.out.println(map.get(A[i]));
        }
    }
}