857.minimum-cost-to-hire-k-workers.md

有 N  名工人。  第  i  名工人的工作质量为  quality[i] ，其最低期望工资为  wage[i] 。

现在我们想雇佣  K  名工人组成一个工资组。在雇佣   一组 K 名工人时，我们必须按照下述规则向他们支付工资：

对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。 工资组中的每名工人至少应当得到他们的最低期望工资。 返回组成一个满足上述条件的工资组至少需要多少钱。

示例 1：

输入： quality = [10,20,5], wage = [70,50,30], K = 2
输出： 105.00000
解释： 我们向 0 号工人支付 70，向 2 号工人支付 35。

示例 2：

输入： quality = [3,1,10,10,1], wage = [4,8,2,2,7], K = 3
输出： 30.66667
解释： 我们向 0 号工人支付 4，向 2 号和 3 号分别支付 13.33333。

提示：

• 1 <= K <= N <= 10000，其中  N = quality.length = wage.length
• 1 <= quality[i] <= 10000
• 1 <= wage[i] <= 10000

与正确答案误差在  10^-5  之内的答案将被视为正确的。

---

算法 1

贪心

• 将所有工人按 工资 / 产出 从小到大 排序
• 优先队列 S 集合 维护 K 个工人组成组成的 花费最小的团队，优先队列按产出从大到小排序
• 枚举 所有工人
  • 当 S 集合元素数量小于 K 时，直接加入集合
  • 当 S 集合元素数量大于等于 K 时，比较当前工人和 S 集合堆顶的工人的产出大小
    • 如果当前工人产出高，直接 pass
    • 如果当前工人产出低，计算堆顶替换成当前工人，是否能够获得花费最小的团队

时间复杂度

对所有工人按性价比从高到低排序 O(nlogn)

枚举每个工人，与堆顶比较 O(nlogK)

总体时间复杂度 O(nlogn)

C++ 代码

class Solution {
public:
    static bool cmp(vector<int>&n1, vector<int>&n2){
        return (double)n1[1] / n1[0] < (double)n2[1] /n2[0];
    }
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
        vector<vector<int>> workers; // 按照性价比 从高到低排序 的集合
        int n = quality.size();
        for (int i = 0; i <n ;i++){
            workers.push_back({quality[i], wage[i]});
        }
        sort(workers.begin(), workers.end(), cmp);

        priority_queue<int> q; // 大顶堆，维护 花费最小的团队的 quelity集合
        int qs = 0; // 总的qualities :越小越好
        double ans = 0x3f3f3f3f;
        for (auto &w: workers){
            if (q.size() < k) {
                q.push(w[0]);
                qs += w[0];
            } else {
                if (w[0] >= q.top()) continue;
                qs = qs - q.top() + w[0];
                q.pop();
                q.push(w[0]);
            }
            if (q.size() == k) ans = min(ans,  (double)qs *w[1] / w[0]);
        }
        return ans;
    }
};