雇佣K工人的最低成本-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

难度:
Hard

题意：

1. n个工人，有一个工作量数组quality，有个最低工资数组wage
2. 要聘用K个工人，工资最低。要求，这n个工人的工资必须不低于他们的最低工资要求，并且他们的工资跟工作量成正比

思路：

- 由于工资跟工作量成正比，假设这个比率是r。第i工人愿意被聘用的条件是r>=wage[i]/quality[i]
- 令ratio[i]=wage[i]/quality[i]，对ratio[i]排序，遍历数组ratio，i每递曾一个，就有一个工人愿意被聘用
- 假设现在有p个工人愿意被聘用(p>=K)，现在轮到我们来挑选K个人，由于工资总和要最低，且工资=工作量*p，所以在这p个人中挑选工作量最低的K个人
- 子问题是，求数列中前K小的数，需要最小堆
- 复杂度是o(nlogn)

代码：

```java
class Solution {
	public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
        double[] ratio = new double[quality.length];
        Integer[] pos = new Integer[quality.length];
        for (int i = 0;i < quality.length;i++) {
            ratio[i] = (double) wage[i] / quality[i];
            pos[i] = i;
        }
        Arrays.sort(pos, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Double.compare(ratio[o1], ratio[o2]);
            }
        });
        double ret = 1e40;
        int maxK = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return -Integer.compare(o1, o2);
            }
        });
        for (int i = 0;i < pos.length;i++) {
            maxK += quality[pos[i]];
            queue.add(quality[pos[i]]);
            if (queue.size() > K) {
                maxK -= queue.poll();
            }
            if (queue.size() == K) {
                ret = ret > maxK * ratio[pos[i]] ? maxK * ratio[pos[i]] : ret;
            }
        }
        return ret;
    }
}
```

该分类下的相关小册推荐：

数据结构与算法(上)

编程之道-算法面试(下)

算法面试通关 50 讲

业务开发实用算法精讲

数据结构与算法之美

编程之道-算法面试(上)

数据结构与算法(下)