首页 > 试题广场 >

牛牛找工作

[编程题]牛牛找工作
  • 热度指数:231 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
为了找到自己满意的工作,牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下,牛牛选择报酬最高的工作。在牛牛选定了自己的工作后,牛牛的小伙伴们来找牛牛帮忙选工作,牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了,于是他只好把这个任务交给了你。

输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数,分别表示工作的数量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.io.File;
import java.util.*;

class Task{
    public int c;
    public int p;
    public Task(int c,int p){
        this.p=p;
        this.c=c;
    }
}
public class Main {
    public static void main(String[] args)throws Exception {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int N=sc.nextInt();
            int M=sc.nextInt();

            List<Task> jobs=new ArrayList<>();

            List<Integer> peoples=new ArrayList<>();
            for(int i=0;i<N;i++){
                int a=sc.nextInt();
                int b=sc.nextInt();
                Task task=new Task(a,b);
                jobs.add(task);
            }
            Collections.sort(jobs,(a,b)->(a.c-b.c));

            for (int i=1;i<N;i++){
                if(jobs.get(i).p<jobs.get(i-1).p){
                    jobs.get(i).p=jobs.get(i-1).p;
                }
            }

            for(int j=0;j<M;j++){
                peoples.add(sc.nextInt());
            }
            for(int j=0;j<M;j++){
                int ans=0;
                int people=peoples.get(j);
                Task tmp=new Task(people,0);
                int index=Collections.binarySearch(jobs,tmp,(a,b)->(a.c-b.c));
                if(index>=0){
                    ans=jobs.get(index).p;
                }else {
                    if(index==-1){
                        ans=0;
                    }else{
                        index=-2-index;
                        ans=jobs.get(index).p;
                    }
                }
                System.out.println(ans);
            }
        }
    }
}

编辑于 2019-08-02 15:26:38 回复(1)