網易2019年實習生筆試題合集《牛牛找工作》 未ac（逾時） 筆記

時間限制：2秒

空間限制：65536K

為了找到自己滿意的工作，牛牛收集了每種工作的難度和報酬。牛牛選工作的标準是在難度不超過自身能力值的情況下，牛牛選擇報酬最高的工作。在牛牛標明了自己的工作後，牛牛的小夥伴們來找牛牛幫忙選工作，牛牛依然使用自己的标準來幫助小夥伴們。牛牛的小夥伴太多了，于是他隻好把這個任務交給了你。 

輸入描述:

每個輸入包含一個測試用例。
每個測試用例的第一行包含兩個正整數，分别表示工作的數量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      

這道題的思考了一會就上手寫了，這也導緻我寫了一下午的時間，血的教訓啊，是以寫題之前一定要考慮清楚在寫題（下次肯定不會上手就寫了）

這道題邏輯上并不難，主要考察的是如何在有限的時間裡，找到最大的工資，時間是個問題，我的代碼逾時了，但是解題思路是一樣的，可以對思路進行參考。

這道題大緻分為3步

1.寫一個數組，記錄工作難度（Di）

2.寫一個Map，用來記錄難度對應的工資（Pi）

3.找出小于等于Di的最大Pi值 就是答案了。

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class 牛牛找工作 {

 


    //可以用二維數組，也可以用HsahMap來存儲，至于比對後面再寫。
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //工作數量
        int N = scanner.nextInt();
        //小夥伴數量
        int M = scanner.nextInt();
        //使用HashMap來存儲工作難度和報酬
        HashMap<Integer,Integer> mWork = new HashMap<>();
        //使用ArrayList記錄難度之後排序；
        int [] DiList =new int[N];
        for (int i = 0; i < N; i++) {
            //難度
            int Di = scanner.nextInt();
            //報酬
            int Pi = scanner.nextInt();
            if(mWork.containsKey(Di)){
                if(mWork.get(Di) < Pi){
                    mWork.replace(Di,Pi);
                }
            }else{
                mWork.put(Di,Pi);
            }
            DiList[i] = Di;
        }
        //存儲完工作和報酬，就要開始通過小夥伴的能力值來判斷工資了。
        //先将ArrayList排序
        Arrays.sort(DiList);

        for (int i = 0; i < M; i++) {

            int MDi = scanner.nextInt();

            int Max = -1;//最大工資
            for (int j = 0; j < N; j++) {
                if(MDi >= DiList[j]){
                    //确定比對範圍。大于Di就不要找了。
                    Max = Math.max(mWork.get(DiList[j]),Max);
                }
            }
            System.out.println(Max);

        }



    }
}
           

通過率是30%，可能是我确定Max的時候複雜度太高所導緻的。