雇佣 K 名工人的最低成本(Leetcode 857)

1

题目分析

   想要求解本题,首先要明白本题的意思,理解题意的时间可能比求解本题还要困难。题意是说每个人都有一个工作质量quality,如果一个人的工作质量是另一个人的两倍,那么他的工资也至少是他的两倍,且要满足最低工资。

我们发现,如果薪水除以工作质量,可以得到时薪

  • 如果两个人的时薪一样,那么两个人的工资一定是一样的。
  • 如果时薪A > B,那么A和B共同选择的时候,支付的钱是按照时薪贵的来算。

以例题来算,第一个工人A的工作质量为10,薪水为70,因此时薪为7元,第三个工人C的工作质量为5,薪水为30,因此时薪为6元。如果按照C的时薪,则第一个人薪水应该发60元,低于70元,不满足条件。因此只能按照A的时薪来算,因为A的时薪高于C,因此折算到C的工作质量,薪水一定高于B

因为W[A] / Q[A] > W[C] / Q[C],所以W[A] / Q[A] x Q[C] > W[C]。

所以按照A的时薪计算出来的结果,一定大于B的期望薪水。所以总花费是(A的工作质量 + B的工作质量) x A的时薪。

所以我们可以从小到大枚举时薪,并使用最大堆存放工作质量,当有一名新的工人被挑选时,时薪肯定会增加,但是工作质量可能会降低(从堆中pop一个最大的工作质量,添加了此名工人的工作质量),因此计算出来的结果可能会变小。

算法的**时间复杂度为O(nlog(n)),空间复杂度为O(n)**。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
int n = quality.length;
int[][] combine = new int[n][2];
for (int i = 0; i < n; i++) {
combine[i][0] = quality[i];
combine[i][1] = wage[i];
}
Arrays.sort(combine, (o1, o2) -> o1[1] * o2[0] - o2[1] * o1[0]);
double cnt = 0;
PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
double res = 1e13;
for (int i = 0; i < k; i++) {
cnt += combine[i][0];
queue.add(combine[i][0]);
}
res = Math.min(res, cnt * combine[k - 1][1] / combine[k - 1][0]);
for (int i = k; i < n; i++) {
if (combine[i][0] < queue.peek()) {
cnt -= queue.poll();
cnt += combine[i][0];
queue.add(combine[i][0]);
res = Math.min(res, cnt * combine[i][1] / combine[i][0]);
}
}
return res;
}
}

刷题总结

  堆是很常用的数据结构,当看到最值时,一定不要忘记它,能够在log(n)的时间复杂度内帮你找到当前集合中的最值。

-------------本文结束感谢您的阅读-------------
0%