857. Minimum Cost to Hire K Workers
857. Minimum Cost to Hire K Workers
题目: https://leetcode.com/problems/minimum-cost-to-hire-k-workers/
难度: Hard
题意：
- n个工人，有一个工作量数组quality，有个最低工资数组wage
- 要聘用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)
代码：
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;
}
}
