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

港控/mmm° 2024-03-29 15:53 48阅读 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;
        }
    }