题目简介：
有 n 名工人。 给定两个数组 quality 和 wage ，其中，quality[i] 表示第 i 名工人的工作质量，其最低期望工资为 wage[i] 。
现在我们想雇佣 k 名工人组成一个工资组。在雇佣 一组 k 名工人时，我们必须按照下述规则向他们支付工资：
- 对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
- 工资组中的每名工人至少应当得到他们的最低期望工资。
给定整数 k ，返回 组成满足上述条件的付费群体所需的最小金额 。在实际答案的 10-5 以内的答案将被接受。
示例 1：
1
2
3
| 输入： quality = [10,20,5], wage = [70,50,30], k = 2
输出： 105.00000
解释： 我们向 0 号工人支付 70，向 2 号工人支付 35。
|
示例 2：
1
2
3
| 输入： quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
输出： 30.66667
解释： 我们向 0 号工人支付 4，向 2 号和 3 号分别支付 13.33333。
|
提示：
n == quality.length == wage.length1 <= k <= n <= 10^41 <= quality[i], wage[i] <= 10^4
思路：
假设我们已经选出了k个人，那么通过价性比（wage / quality）可以知道，最后的雇佣成本为k个人中最高的价性比 * k个人的总工作质量（也只有这样，才能满足条件2）。
那么我们所需要做的，便是遍历所有可能出现的k个人，并获得最小的雇佣成本。
我们先通过价性比从低到高排序k个人。并累加前k - 1个人的工作质量，然后遍历剩余的所有人，每次组成k个人时，记录当前的雇佣成本。然后删除工作质量最高的人来获取更低的雇佣成本（此时为新的k-1个人）。依次类推，得到最后的结果。
tips:
- 通过优先队列对工作质量进行降序排序，方便删除。
- 由于会出现小数，需要注意
int和double的转换
代码如下：
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
29
30
31
32
33
34
35
36
37
| class Solution {
public:
double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
vector<int> idxs(quality.size());
for(int i = 0; i < idxs.size(); i++)
idxs[i] = i;
sort(idxs.begin(), idxs.end(), [&](int& a, int& b) {
return wage[a] * 1.0 / quality[a] * 1.0 < wage[b] * 1.0 / quality[b] * 1.0;
});
priority_queue<int, vector<int>, less<int>> qu;
double quality_all = 0;
for(int i = 0; i < k - 1; i++){
quality_all += quality[idxs[i]];
qu.push(quality[idxs[i]]);
}
double res = 1e9;
for(int i = k - 1; i < quality.size(); i++){
quality_all += quality[idxs[i]];
qu.push(quality[idxs[i]]);
res = min(res, quality_all * (wage[idxs[i]] * 1.0 / quality[idxs[i]] * 1.0));
quality_all -= qu.top();
qu.pop();
}
return res;
}
};
|
