题目描述
有 N
名工人。第 i
名工人的工作质量为 quality[i]
,其最低期望工资为 wage[i]
。
现在我们想雇佣 K
名工人组成一个工资组。在雇佣一组 K
名工人时,我们必须按照下述规则向他们支付工资:
- 对工资组中的每名工人,应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
- 工资组中的每名工人至少应当得到他们的最低期望工资。
返回组成一个满足上述条件的工资组至少需要多少钱。
样例
输入: quality = [10,20,5], wage = [70,50,30], K = 2
输出: 105.00000
解释: 我们向 0 号工人支付 70,向 2 号工人支付 35。
输入: quality = [3,1,10,10,1], wage = [4,8,2,2,7], K = 3
输出: 30.66667
解释: 我们向 0 号工人支付 4,向 2 号和 3 号分别支付 13.33。
注意
- 1 <= K <= N <= 10000,其中 N = quality.length = wage.length
- 1 <= quality[i] <= 10000
- 1 <= wage[i] <= 10000
- 与正确答案误差在 10^-5 之内的答案将被视为正确的。
算法
(贪心) $O(n \log n)$
- 根据所有人的性价比进行倒序排序。排序后,选定第 $i$ 个人作为 base 发工资时,1 到 $i-1$ 的人的工资最低标准总能被满足。
- 枚举每个人作为 base,当枚举到第 $i$ 个人时,我们期望发的工资最少,此时工资总和与质量有关,所以我们在前 $i-1$ 个人中选取质量最低的 $K$ 个人,即可获得以第 $i$ 个人为 base 时的最低工资总和。
- 用堆来维护质量最低的 $K$ 个人,同时用一个变量来记录此时堆中所有人的质量总和。
时间复杂度
- 排序需要 $O(n \log n)$ 的时间。
- 枚举 $n$ 个人,每次枚举寻找最大值时间复杂度为常数,弹出质量最高的人并将第 $i$ 个人插入堆中的时间复杂度为 $O(\log K)$。
- 故总时间复杂度为 $O(n \log n)$。
C++ 代码
class Solution {
public:
double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int K) {
int n = quality.size();
vector<pair<double, int>> r(n);
for (int i = 0; i < n; i++)
r[i] = make_pair(1.0 * quality[i] / wage[i], i);
sort(r.begin(), r.end());
reverse(r.begin(), r.end());
priority_queue<pair<int, int>> heap;
double ans = 1e10;
int sum = 0;
for (int i = 0; i < n; i++) {
double tmp = wage[r[i].second];
double ratio = 1.0 * wage[r[i].second] / quality[r[i].second];
if (heap.size() == K - 1) {
ans = min(ans, tmp + sum * ratio);
}
if (K > 1) {
if (heap.size() < K - 1) {
heap.push(make_pair(quality[r[i].second], r[i].second));
sum += quality[r[i].second];
}
else {
if (quality[r[i].second] < heap.top().first) {
sum -= heap.top().first;
heap.pop();
heap.push(make_pair(quality[r[i].second], r[i].second));
sum += quality[r[i].second];
}
}
}
}
return ans;
}
};
时间复杂度是 O(nlogn),一开始的排序没算进去
感谢指出,已修正
感觉这个不是贪心吧,是遍历以i为base所有情况找到n个最优解中的最优解,得出来的一定是最优解