首页 > 试题广场 >

牛牛找工作

[编程题]牛牛找工作

热度指数：4823 时间限制：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)。
保证不存在两项工作的报酬相同。

输出描述:

对于每个小伙伴，在单独的一行输出一个整数表示他能得到的最高报酬。如果他找不到工作，则输出0。一个工作可以被多个人选择。

示例1

输入

3 3 
1 100 
10 1000 
1000000000 1001 
9 10 1000000000

输出

100 
1000 
1001

算法知识视频讲解

Java

codeasn

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

public class Main {
    private static int[][] Jobs;
    private static int N, M;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();//工作
        M = sc.nextInt();//人
        Jobs = new int[N][2];
        for (int i = 0; i < N; ++i) {
            Jobs[i][0] = sc.nextInt();
            Jobs[i][1] = sc.nextInt();
        }
        Arrays.sort(Jobs, (int[] a, int[] b) -> {
            return a[0] - b[0];
        });
        for (int i = 1; i < N; i++) {
            Jobs[i][1] = Math.max(Jobs[i][1], Jobs[i - 1][1]);
        }
        for (int i = 0; i < M; i++) {
            int ai = sc.nextInt();
            if (ai < Jobs[0][0]) {
                System.out.println(0);
            } else if (ai >= Jobs[N - 1][0]) {
                System.out.println(Jobs[N - 1][1]);
            } else {
                binarySearch(ai);
            }
        }
    }

    private static void binarySearch(int ai) {
        int lo = 0;
        int hi = N;
        //第一个大于
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (Jobs[mid][0] < ai) {
                lo = mid + 1;
            } else if (Jobs[mid][0] > ai) {
                hi = mid;
            } else {
                System.out.println(Jobs[mid][1]);
                return;
            }
        }
        System.out.println(Jobs[hi - 1][1]);//最后一个不大于
    }
}

编辑于 2020-02-15 21:38:15 回复(0)