题目分析
想要求解本题,首先要明白本题的意思,理解题意的时间可能比求解本题还要困难。题意是说每个人都有一个工作质量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 | class Solution { |
刷题总结
堆是很常用的数据结构,当看到最值时,一定不要忘记它,能够在log(n)的时间复杂度内帮你找到当前集合中的最值。