一、题目
1、题目描述
为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了，于是他只好把这个任务交给了你。
输入描述：
每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数，分别表示工作的数量N(N<=100000)和小伙伴的数量M(M<=100000)。
接下来的N行每行包含两个正整数，分别表示该项工作的难度Di(Di<=1000000000)和报酬Pi(Pi<=1000000000)。
接下来的一行包含M个正整数，分别表示M个小伙伴的能力值Ai(Ai<=1000000000)。
保证不存在两项工作的报酬相同。输出描述：
对于每个小伙伴，在单独的一行输出一个正整数表示他能得到的最高报酬。一个工作可以被多个人选择。
2、示例
示例1：
输入
3 3
1 100
10 1000
1000000000 1001
9 10 1000000000输出
100
1000
1001
二、解题思路
1、思路一
找到难度不大于能力的所有工作里，报酬最多的。核心是用HashMap来记录难度和不超过该难度的最大报酬。
先把工作的难度和报酬映射到HashMap,把人的能力也全部读进来，放到HashMap，报酬可以先设为0.
最后按难度从小到大（所以需要先排序）更新HashMap,key为难度，value为不超过难度的最大报酬。
三、代码
1、思路一代码
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int workAmount,palAmount=0;
workAmount=in.nextInt();
palAmount=in.nextInt();
HashMap<Integer,Integer> diPi=new HashMap<>();
int di,pi=0;
int[] diAndAi=new int[workAmount+palAmount];
int[] ai=new int[palAmount];
for(int i=0;i<workAmount;i++){
di=in.nextInt();
pi=in.nextInt();
if(diPi.containsKey(di)){
pi=Math.max(pi,diPi.get(di));
}
diAndAi[i]=di;
diPi.put(di,pi);
}
for(int i=0;i<palAmount;i++){
di=in.nextInt();
diAndAi[workAmount+i]=di;
if(!diPi.containsKey(di)){
diPi.put(di,0);
}
ai[i]=di;
}
Arrays.sort(diAndAi);
int max=0;
for(int i=0;i<workAmount+palAmount;i++){
max=Math.max(max,diPi.get(diAndAi[i]));
diPi.put(diAndAi[i],max);
}
for(int i=0;i<palAmount;i++){
System.out.println(diPi.get(ai[i]));
}
}
}
本文设计引用来自于nowcoder牛客网
