题目描述

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

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

1. 对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
2. 工资组中的每名工人至少应当得到他们的最低期望工资。

返回组成一个满足上述条件的工资组至少需要多少钱。

样例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. 1 <= K <= N <= 10000，其中 N = quality.length = wage.length
2. 1 <= quality[i] <= 10000
3. 1 <= wage[i] <= 10000
4. 与正确答案误差在 10^-5 之内的答案将被视为正确的。

算法

(排序+堆) $O(n\log n)$

首先一个工资组内的工人的工资与他们的工作质量是等比的，也就是说 $\frac{q_i}{q_j}=\frac{w_i}{w_j}\Rightarrow \frac{w_i}{q_i} = \frac{w_j}{q_j} = x$，这里的 $x$ 为组内的工资系数，即 $ w_i = x \times q_i$。另外每一个人的工资需要不低于他们的最低期望工资，即 $x \times q_i \ge w_i \Rightarrow x \ge \frac{w_i}{q_i}$。

这样我们可以先枚举组内的工资系数 $x$，然后求 K 个工人满足 $\frac{w_i}{q_i} \le x$ 并且使得 $\sum q_i$ 最小。因为答案里的 $x$ 一定为组内某一个人的 $\frac{w_i}{q_i}$，否则我们可以降低 $x$ 至某一个 $\frac{w_i}{q_i}$ 使得组内的工资和降低并且依然满足每个人的工资要求，所以我们枚举 $\frac{w_i}{q_i}$ 即可，具体做法如下：

我们先将数组按照 $\frac{w_i}{q_i}$ 升序排序，然后从小到大枚举每个 $\frac{w_i}{q_i}$ 作为组内的工资系数，同时用一个大根堆来维护[0, i]中quality最小的 K 个人以及他们quality的和。注意这 K 个人里可能不包含我们当前枚举的第i个人，但是这并不会影响答案的正确性，因为这种做法保证了一定能搜索到答案（答案的定义就是以某一个 $\frac{w_i}{q_i}$ 为工资系数并且使得这 K 个人在 [0, i]中quality的和最小，当我们枚举到答案的 $\frac{w_i}{q_i}$ 时，用大根堆维护的这 K 个人就是quality和最小的人）。

时间复杂度

排序需要 $O(n\log n)$ 的复杂度，枚举数组的复杂度为 $O(n\log K)$，总时间复杂度为 $O(n\log n)$。

C++ 代码

class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int K) {
        vector<pair<double, int>> radio;
        for (int i = 0; i < wage.size(); i ++ ) {
            radio.push_back({wage[i] * 1.0 / quality[i], i});
        }
        sort(radio.begin(), radio.end());

        priority_queue<int> heap;
        double res = 1e9;
        int sum = 0;
        for (int i = 0; i < radio.size(); i ++ ) {
            heap.push(quality[radio[i].second]);
            sum += quality[radio[i].second];
            if (heap.size() > K) {
                sum -= heap.top();
                heap.pop();
            }
            if (heap.size() == K) res = min(res, sum * radio[i].first);
        }
        return res;
    }
};