class Solution {
public:
double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
}
};
857. 雇佣 K 名工人的最低成本
有 n 名工人。 给定两个数组 quality 和 wage ，其中，quality[i] 表示第 i 名工人的工作质量，其最低期望工资为 wage[i] 。
现在我们想雇佣 k 名工人组成一个工资组。在雇佣 一组 k 名工人时，我们必须按照下述规则向他们支付工资：
给定整数 k ，返回 组成满足上述条件的付费群体所需的最小金额 。在实际答案的 10-5 以内的答案将被接受。。
示例 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。
提示：
n == quality.length == wage.length1 <= k <= n <= 1041 <= quality[i], wage[i] <= 104原站题解
rust 解法, 执行用时: 4 ms, 内存消耗: 2.2 MB, 提交时间: 2024-05-02 13:52:51
use std::collections::BinaryHeap;
impl Solution {
pub fn mincost_to_hire_workers(quality: Vec<i32>, wage: Vec<i32>, k: i32) -> f64 {
let n = quality.len();
let k = k as usize;
let mut id = (0..n).collect::<Vec<_>>();
// 按照 r 值排序
id.sort_unstable_by(|&i, &j| (wage[i] * quality[j]).cmp(&(wage[j] * quality[i])));
let mut h = BinaryHeap::new();
let mut sum_q = 0;
for i in 0..k {
h.push(quality[id[i]]);
sum_q += quality[id[i]];
}
// 选 r 值最小的 k 名工人
let mut ans = sum_q as f64 * wage[id[k - 1]] as f64 / quality[id[k - 1]] as f64;
// 后面的工人 r 值更大
// 但是 sum_q 可以变小，从而可能得到更优的答案
for i in k..n {
let q = quality[id[i]];
if q < *h.peek().unwrap() {
sum_q -= h.pop().unwrap() - q;
h.push(q);
ans = ans.min(sum_q as f64 * wage[id[i]] as f64 / q as f64);
}
}
ans
}
}
javascript 解法, 执行用时: 140 ms, 内存消耗: 47.6 MB, 提交时间: 2023-09-25 17:43:11
/**
* @param {number[]} quality
* @param {number[]} wage
* @param {number} k
* @return {number}
*/
var mincostToHireWorkers = function(quality, wage, k) {
const n = quality.length;
const h = new Array(n).fill(0).map((_, i) => i);
h.sort((a, b) => {
return quality[b] * wage[a] - quality[a] * wage[b]; //
});
let res = 1e9;
let totalq = 0.0;
const pq = new MaxPriorityQueue();
for (let i = 0; i < k - 1; i++) {
totalq += quality[h[i]];
pq.enqueue(quality[h[i]]);
}
for (let i = k - 1; i < n; i++) {
let idx = h[i];
totalq += quality[idx];
pq.enqueue(quality[idx]);
const totalc = (wage[idx] / quality[idx]) * totalq;
res = Math.min(res, totalc);
totalq -= pq.dequeue().element;
}
return res;
};
golang 解法, 执行用时: 32 ms, 内存消耗: 6.3 MB, 提交时间: 2023-09-25 17:42:29
func mincostToHireWorkers(quality, wage []int, k int) float64 {
type pair struct{ q, w int }
qw := make([]pair, len(quality))
for i, q := range quality {
qw[i] = pair{q, wage[i]}
}
sort.Slice(qw, func(i, j int) bool { a, b := qw[i], qw[j]; return a.w*b.q < b.w*a.q }) // 按照 r 值排序
h := hp{make([]int, k)}
sumQ := 0
for i, p := range qw[:k] {
h.IntSlice[i] = p.q
sumQ += p.q
}
heap.Init(&h)
ans := float64(sumQ*qw[k-1].w) / float64(qw[k-1].q) // 选 r 值最小的 k 名工人组成当前的最优解
for _, p := range qw[k:] {
if p.q < h.IntSlice[0] { // sumQ 可以变小，从而可能得到更优的答案
sumQ -= h.IntSlice[0] - p.q
h.IntSlice[0] = p.q
heap.Fix(&h, 0) // 更新堆顶
ans = math.Min(ans, float64(sumQ*p.w)/float64(p.q))
}
}
return ans
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] } // 最大堆
func (hp) Push(interface{}) {} // 由于没有用到，可以什么都不写
func (hp) Pop() (_ interface{}) { return }
cpp 解法, 执行用时: 40 ms, 内存消耗: 19.9 MB, 提交时间: 2023-09-25 17:42:06
class Solution {
public:
double mincostToHireWorkers(vector<int> &quality, vector<int> &wage, int k) {
int n = quality.size(), id[n], sum_q = 0;
iota(id, id + n, 0);
sort(id, id + n, [&](int i, int j) { return wage[i] * quality[j] < wage[j] * quality[i]; }); // 按照 r 值排序
priority_queue<int> pq;
for (int i = 0; i < k; ++i) {
pq.push(quality[id[i]]);
sum_q += quality[id[i]];
}
double ans = sum_q * ((double) wage[id[k - 1]] / quality[id[k - 1]]); // 选 r 值最小的 k 名工人组成当前的最优解
for (int i = k; i < n; ++i)
if (int q = quality[id[i]]; q < pq.top()) { // sum_q 可以变小，从而可能得到更优的答案
sum_q -= pq.top() - q;
pq.pop();
pq.push(q);
ans = min(ans, sum_q * ((double) wage[id[i]] / q));
}
return ans;
}
};
java 解法, 执行用时: 29 ms, 内存消耗: 43.2 MB, 提交时间: 2023-09-25 17:41:29
class Solution {
public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
int n = quality.length, sumQ = 0;
var id = IntStream.range(0, n).boxed().toArray(Integer[]::new);
Arrays.sort(id, (i, j) -> wage[i] * quality[j] - wage[j] * quality[i]); // 按照 r 值排序
var pq = new PriorityQueue<Integer>((a, b) -> b - a); // 最大堆
for (var i = 0; i < k; ++i) {
pq.offer(quality[id[i]]);
sumQ += quality[id[i]];
}
var ans = sumQ * ((double) wage[id[k - 1]] / quality[id[k - 1]]); // 选 r 值最小的 k 名工人组成当前的最优解
for (var i = k; i < n; ++i) {
var q = quality[id[i]];
if (q < pq.peek()) { // sumQ 可以变小，从而可能得到更优的答案
sumQ -= pq.poll() - q;
pq.offer(q);
ans = Math.min(ans, sumQ * ((double) wage[id[i]] / q));
}
}
return ans;
}
// 官方
public double mincostToHireWorkers2(int[] quality, int[] wage, int k) {
int n = quality.length;
Integer[] h = new Integer[n];
for (int i = 0; i < n; i++) {
h[i] = i;
}
Arrays.sort(h, (a, b) -> {
return quality[b] * wage[a] - quality[a] * wage[b];
});
double res = 1e9;
double totalq = 0.0;
PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
for (int i = 0; i < k - 1; i++) {
totalq += quality[h[i]];
pq.offer(quality[h[i]]);
}
for (int i = k - 1; i < n; i++) {
int idx = h[i];
totalq += quality[idx];
pq.offer(quality[idx]);
double totalc = ((double) wage[idx] / quality[idx]) * totalq;
res = Math.min(res, totalc);
totalq -= pq.poll();
}
return res;
}
}
python3 解法, 执行用时: 88 ms, 内存消耗: 18.1 MB, 提交时间: 2023-09-25 17:40:22
class Solution:
def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
qw = sorted(zip(quality, wage), key=lambda p: p[1] / p[0]) # 按照 r 值排序
h = [-q for q, _ in qw[:k]] # 加负号变成最大堆
heapify(h)
sum_q = -sum(h)
ans = sum_q * qw[k - 1][1] / qw[k - 1][0] # 选 r 值最小的 k 名工人组成当前的最优解
for q, w in qw[k:]:
if q < -h[0]: # sum_q 可以变小，从而可能得到更优的答案
sum_q += heapreplace(h, -q) + q # 更新堆顶和 sum_q
ans = min(ans, sum_q * w / q)
return ans
# 贪心 + 优先队列（最小堆）
def mincostToHireWorkers2(self, quality: List[int], wage: List[int], k: int) -> float:
pairs = sorted(zip(quality, wage), key=lambda p: p[1] / p[0])
ans = inf
totalq = 0
h = []
for q, w in pairs[:k - 1]:
totalq += q
heappush(h, -q)
for q, w in pairs[k - 1:]:
totalq += q
heappush(h, -q)
ans = min(ans, w / q * totalq)
totalq += heappop(h)
return ans