概览
给定N个工人，每个工人有一个quality值和一个wage值，要求在N个工人中雇佣K个人，并按照如下标准发放工资：
- 每个人被发放的工资
pay与quality的比值必须相同。 - 每个人被发放的工资
pay必须大于wage。
求总工资的最小值。
题解
首先，对题目中的两个条件进行解读。
由题中第一个条件可知：
选定的K个人中，每人发放的实际工资pay与quality的比值相同。
定义价性比ratio = wage / quality，表达每个工人单位quality期望的工资，定义实际价性比ratio_ = pay / quality，那么由题中第二个条件可知：
选定的K个人中，每人发放的实际工资pay与quality的比值必须大于ratio。
综上所述，可得本题关键性的信息：
选定的K个人中，ratio_ >= max{ratio}，即实际价性比不得低于雇佣的工人中最高的期望价性比。
又因为总工资cost = ratio_ * sum(quality)，所以要使得总工资尽可能的小，就要使ratio_和sum(quality)尽可能小，因此可得具体的算法流程如下：
- 对所有人按价性比进行排序。
- 选择价性比最低的前
K个人作为初始集，计算总工资。 - 从第
K + 1个人开始，循环如下过程直至无人可以添加：- 踢出原集合中
quality最大的工人，并添加该新工人。 - 重新计算
quality的总和。 - 重新计算总工资，若小于当前最小值，则更新该值。
- 踢出原集合中
上述算法本质即遍历所有可能的价性比，找出最小的总工资。
复杂度分析
本题的空间复杂度为$O(N)$，但时间复杂度并不那么直观，需要逐步分析。
- 对所有人的价性比进行排序。（$O(NlogN)$）
- 选择价性比最低的前
K个人作为初始集，计算总工资。（$O(N)$） - 从第
K + 1个人开始，循环如下过程直至无人可以添加：（$O(N)$）- 踢出原集合中
quality最大的工人，并添加该新工人。（$O(logN)$） - 重新计算
quality的总和。（$O(1)$） - 重新计算总工资，若小于当前最小值，则更新该值。（$O(1)$）
- 踢出原集合中
其中步骤3.1的复杂度依赖于具体实现方式，使用优先队列实现可以保证复杂度为$O(logN)$。
步骤3.2只需要取出踢出的工人和新工人的quality值即可计算，复杂度为常数时间。
步骤3.3中用新工人的ratio作为总ratio_进行计算，复杂度为常数时间。
综上所述，时间复杂度为$O(NlogN)$，空间复杂度为$O(N)$。