给定数组hard和money，长度都为N；hard[i]表示i号的难度， money[i]表示i号工作的收入；给定数组ability，长度都为M，ability[j]-蒲公英云

给定数组hard和money，长度都为N；hard[i]表示i号的难度， money[i]表示i号工作的收入；给定数组ability，长度都为M，ability[j]

港控/mmm° 2024-03-29 15:53 132阅读 0赞

题目描述

给定数组hard和money，长度都为N；hard[i]表示i号的难度， money[i]表示i号工作的收入；给定数组ability，长度都为M，ability[j]表示j号人的能力；每一号工作，都可以提供无数的岗位，难度和收入都一样；但是人的能力必须>=这份工作的难度，才能上班。返回一个长度为M的数组ans，ans[j]表示j号人能获得的最好收入。

题目分析

数组hard: [7, 1, 1, 3]
数组money: [13, 5, 9, 6]
将hard和money按照hard排序，如果hard相等，钱多的放前面
(1, 9) (1, 5) (3, 6) (7, 13)
1.对于上面的排序，如果hard相同，那么肯定选择money大的
因此：(1, 9) (3, 6) (7, 13)
2.如果难度增加了，但是钱变小了，那么没必要选择钱少的
因此：(1, 9) (7, 13)
题目思路：先排序，然后放入TreeMap中，如果相同的，只放最大值，不同的，只放递增的

import java.util.*;
public class ChooseWork {
    public static class Job{
        public int hard;
        public int money;
        public Job(int hard,int money){
            this.hard = hard;
            this.money = money;
        }
    }
    public static class JobComparator implements Comparator<Job>{
        @Override
        public int compare(Job o1, Job o2) {
            //如果hard不等，我们选择money降序，hard相等，money升序
            return o1.hard!=o2.hard?(o1.hard-o2.hard):(o2.money-o1.money);
        }
    }
    //贪心+有序表
    public static int[] getMoneys(Job[] job,int[] ability){
        Arrays.sort(job,new JobComparator());
        // key : 难度   value：报酬
        TreeMap<Integer, Integer> map = new TreeMap<>();
        map.put(job[0].hard,job[0].money);
        // pre : 上一份进入map的工作
        Job pre = job[0];
        for (int i = 1; i < job.length; i++) {
            if (job[i].hard != pre.hard && job[i].money > pre.money){
                pre = job[i];
                map.put(pre.hard,pre.money);
            }
        }
        int[] ans = new int[ability.length];
        for (int i = 0; i < ability.length; i++) {
            // ability[i] 当前人的能力 <= ability[i]  且离它最近的
            Integer key = map.floorKey(ability[i]);
            ans[i] = key != null ? map.get(key):0;
        }
        return ans;
    }
    //暴力解
    public static int[] getMoneys2(Job[] job,int[] ability){
        Arrays.sort(job,new JobComparator());
        // key : 难度   value：报酬
        int[] ans = new int[ability.length];
        for (int i = 0; i < ability.length; i++) {
            int abilityHard = ability[i];
            int moneyMax = Integer.MIN_VALUE;
            if (abilityHard >=job[0].hard){
                moneyMax = job[0].money;
                for (int j = 1; j < job.length; j++) {
                    if (abilityHard >=job[j].hard){
                        if (moneyMax < job[j].money){
                            moneyMax = job[j].money;
                        }
                    }
                }
            }else {
                ans[i] = 0;
            }
            ans[i] = moneyMax;
        }
        return ans;
    }
    //test
    public static void main(String[] args) {
        Random random = new Random();
        Job[] jobs = new Job[1000];
        int[] ability = new int[500];
        for (int i = 0; i < jobs.length; i++) {
            jobs[i] = new Job(random.nextInt(100), random.nextInt(100));
        }
        for (int i = 0; i < ability.length; i++){
            ability[i] = random.nextInt(100);
        }
        if (!equals(getMoneys(jobs,ability),getMoneys2(jobs,ability))){
            System.out.println("Oops");
        }
    }
    //test
    private static boolean equals(int[] arr1, int[] arr2) {
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] == arr2[i]){
                return true;
            }
        }
        return false;
    }
}