1
2023-05-18：有 n 名工人。 给定两个数组 quality 和 wage ， 其中，quality[i] 表示第 i 名工人的工作质量，其最低期望工资为 wage[i] 。 现在我们想雇佣
作者：福大大架构师每日一题
- 2023-05-18 北京
本文字数：4905 字
阅读完需：约 16 分钟
2023-05-18：有 n 名工人。 给定两个数组 quality 和 wage ，
其中，quality[i] 表示第 i 名工人的工作质量，其最低期望工资为 wage[i] 。
现在我们想雇佣 k 名工人组成一个工资组。在雇佣 一组 k 名工人时，
我们必须按照下述规则向他们支付工资：
对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
工资组中的每名工人至少应当得到他们的最低期望工资。
给定整数 k ，返回 组成满足上述条件的付费群体所需的最小金额。
输入： quality = [10,20,5], wage = [70,50,30], k = 2。
输出： 105.00000。
答案 2023-05-18：
解题步骤：
1.构造 Employee 结构体，存储每个员工的工作质量和垃圾系数（wage / quality）。
2.按照垃圾系数从小到大对所有员工进行排序。
3.维护一个大小为 k 的小根堆，表示当前最低期望工资组中的 k 名工人的工作质量。
4.遍历所有员工，如果堆未满，则将该员工加入堆中并更新最低期望工资。如果堆已满，则检查当前员工能否替换堆顶元素，如果可以，则弹出堆顶元素并将当前员工入堆，更新最低期望工资。
5.最终返回最低期望工资即可。
注意事项：
使用 golang 内置的 container/heap 库来实现小根堆。
在比较垃圾系数大小时，需要使用小于等于号，因为可能存在两个员工的垃圾系数完全相等的情况。
时间复杂度：排序所需的时间为 O(nlogn)，遍历员工数组时每个员工会入堆一次，出堆一次，即共进行了 2n 次操作，而小根堆的插入和弹出操作时间复杂度均为 O(logk)，因此总时间复杂度为 O(nlogn + nlogk)。
空间复杂度：除给定数组外，我们还需要构造 Employee 结构体，以及维护大小为 k 的小根堆，因此需要额外使用 O(n) 空间来存储结构体数组，并且在堆满时可能需要对堆进行调整，最多需要 O(k) 的额外空间。因此总空间复杂度为 O(n + k)。
go 完整代码如下：
package main
import ( "container/heap" "fmt" "sort")
type Employee struct { RubbishDegree float64 Quality int}
func NewEmployee(w, q int) Employee { return Employee{RubbishDegree: float64(w) / float64(q), Quality: q}}
type EmployeeHeap []int
func (h EmployeeHeap) Len() int { return len(h) }func (h EmployeeHeap) Less(i, j int) bool { return h[i] > h[j] }func (h EmployeeHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }func (h *EmployeeHeap) Push(x interface{}) { *h = append(*h, x.(int)) }func (h *EmployeeHeap) Pop() interface{} { n := len(*h) x := (*h)[n-1] *h = (*h)[:n-1] return x}
func min(a, b float64) float64 { if a < b { return a } return b}
func mincostToHireWorkers(quality []int, wage []int, k int) float64 { n := len(quality) employees := make([]Employee, n) for i := range quality { employees[i] = NewEmployee(wage[i], quality[i]) } sort.Slice(employees, func(i, j int) bool { return employees[i].RubbishDegree <= employees[j].RubbishDegree }) minTops := &EmployeeHeap{} heap.Init(minTops) ans, qualitySum := 1e9, 0 for i := 0; i < n; i++ { curQuality := employees[i].Quality if minTops.Len() < k { // 堆没满 qualitySum += curQuality heap.Push(minTops, curQuality) if minTops.Len() == k { ans = min(ans, float64(qualitySum)*employees[i].RubbishDegree) } } else { // 来到当前员工的时候，堆是满的！ // 当前员工的能力，可以把堆顶干掉，自己进来！ if top := (*minTops)[0]; top > curQuality { heap.Pop(minTops) qualitySum += curQuality - top heap.Push(minTops, curQuality) ans = min(ans, float64(qualitySum)*employees[i].RubbishDegree) } } } return ans}
func main() { quality := []int{10, 20, 5} wage := []int{70, 50, 30} k := 2 result := mincostToHireWorkers(quality, wage, k) fmt.Println(result)}
复制代码
rust 完整代码如下：
struct Employee { rubbish_degree: f64, quality: i32,}
impl Employee { fn new(w: i32, q: i32) -> Self { let rubbish_degree = w as f64 / q as f64; Self { rubbish_degree, quality: q, } }}
fn mincost_to_hire_workers(quality: Vec<i32>, wage: Vec<i32>, k: i32) -> f64 { let n = quality.len(); let mut employees = Vec::with_capacity(n); for i in 0..n { employees.push(Employee::new(wage[i], quality[i])); } // 只根据垃圾指数排序 // 要价 / 能力 employees.sort_by(|a, b| a.rubbish_degree.partial_cmp(&b.rubbish_degree).unwrap()); // 请维持力量最小的前K个力量 // 大根堆！门槛堆！ let mut min_tops = std::collections::BinaryHeap::new(); let mut ans = std::f64::MAX; let mut quality_sum = 0; for i in 0..n { // i : 依次所有员工的下标 // quality_sum : 进入堆的力量总和！ // cur_quality当前能力 let cur_quality = employees[i].quality; if min_tops.len() < k as usize { // 堆没满 quality_sum += cur_quality; min_tops.push(cur_quality); if min_tops.len() == k as usize { ans = ans.min(quality_sum as f64 * employees[i].rubbish_degree); } } else { // 来到当前员工的时候，堆是满的！ // 当前员工的能力，可以把堆顶干掉，自己进来！ if let Some(top) = min_tops.peek() { if *top > cur_quality { quality_sum += cur_quality - min_tops.pop().unwrap(); min_tops.push(cur_quality); ans = ans.min(quality_sum as f64 * employees[i].rubbish_degree); } } } } ans}
fn main() { let quality = vec![10, 20, 5]; let wage = vec![70, 50, 30]; let k = 2; let result = mincost_to_hire_workers(quality, wage, k); println!("{}", result);}
复制代码
c 完整代码如下：
#include <stdio.h>#include <stdlib.h>#include <limits.h>
typedef struct Employee { double rubbishDegree; int quality;} Employee;
int cmp(const void* a, const void* b) { Employee* pa = (Employee*)a; Employee* pb = (Employee*)b; if (pa->rubbishDegree < pb->rubbishDegree) { return -1; } else if (pa->rubbishDegree > pb->rubbishDegree) { return 1; } else { return 0; }}
double mincostToHireWorkers(int* quality, int qualitySize, int* wage, int wageSize, int k) { int n = qualitySize; Employee* employees = (Employee*)malloc(n * sizeof(Employee)); for (int i = 0; i < n; i++) { employees[i].quality = quality[i]; employees[i].rubbishDegree = (double)wage[i] / (double)quality[i]; } qsort(employees, n, sizeof(Employee), cmp); int* minTops = (int*)malloc(k * sizeof(int)); int topIndex = -1; double ans = INT_MAX; int qualitySum = 0; for (int i = 0; i < n; i++) { int curQuality = employees[i].quality; if (topIndex < k - 1) { qualitySum += curQuality; minTops[++topIndex] = curQuality; if (topIndex == k - 1) { ans = qualitySum * employees[i].rubbishDegree; } } else { if (minTops[0] > curQuality) { qualitySum += curQuality - minTops[0]; minTops[0] = curQuality; ans = qualitySum * employees[i].rubbishDegree; // 调整，使堆继续保持最小堆的性质 for (int j = 0; j < k - 1; j++) { if (minTops[j] > minTops[j + 1]) { int tmp = minTops[j]; minTops[j] = minTops[j + 1]; minTops[j + 1] = tmp; } else { break; } } } } } free(employees); free(minTops); return ans;}
int main() { int quality[] = { 10,20,5 }; int wage[] = { 70,50,30 }; int k = 2; double result = mincostToHireWorkers(quality, sizeof(quality) / sizeof(int), wage, sizeof(wage) / sizeof(int), k); printf("%lf\n", result); return 0;}
复制代码
c++完整代码如下：
#include <iostream>#include <vector>#include <queue>#include <algorithm>#include <limits>
using namespace std;
struct Employee { double rubbishDegree; int quality; Employee() = default; Employee(int w, int q) : rubbishDegree(static_cast<double>(w) / static_cast<double>(q)), quality(q) {} bool operator<(const Employee& other) const { return rubbishDegree < other.rubbishDegree; }};
double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) { int n = quality.size(); vector<Employee> employees(n); for (int i = 0; i < n; i++) { employees[i] = Employee(wage[i], quality[i]); } // 只根据垃圾指数排序 sort(employees.begin(), employees.end()); // 请维持力量最小的前K个力量 // 大根堆！门槛堆！ priority_queue<int> minTops; double ans = numeric_limits<double>::max(); for (int i = 0, qualitySum = 0; i < n; i++) { // i : 依次所有员工的下标 // qualitySum : 进入堆的力量总和！ // curQuality当前能力 int curQuality = employees[i].quality; if (minTops.size() < k) { // 堆没满 qualitySum += curQuality; minTops.push(curQuality); if (minTops.size() == k) { ans = min(ans, qualitySum * employees[i].rubbishDegree); } } else { // 来到当前员工的时候，堆是满的！ // 当前员工的能力，可以把堆顶干掉，自己进来！ if (minTops.top() > curQuality) { // qualitySum -= minTops.top(); // qualitySum += curQuality; // minTops.pop(); // minTops.push(curQuality); qualitySum += curQuality - minTops.top(); minTops.pop(); minTops.push(curQuality); ans = min(ans, qualitySum * employees[i].rubbishDegree); } } } return ans;}
int main() { vector<int> quality = { 10, 20, 5 }; vector<int> wage = { 70, 50, 30 }; int k = 2; double result = mincostToHireWorkers(quality, wage, k); cout << result << endl; // 105 return 0;}
复制代码
划线
评论
复制
发布于: 2 小时前阅读数: 8
版权声明: 本文为 InfoQ 作者【福大大架构师每日一题】的原创文章。
原文链接:【http://xie.infoq.cn/article/7bb49ed8d5c932951ee506c3f】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
福大大架构师每日一题
关注
公众号：福大大架构师每日一题 2021-02-15 加入
公众号：福大大架构师每日一题
![2023-05-18：有 n 名工人。 给定两个数组 quality 和 wage ， 其中，quality[i] 表示第 i 名工人的工作质量，其最低期望工资为 wage[i] 。 现在我们想雇佣_Go_福大大架构师每日一题_InfoQ写作社区](https://static001.infoq.cn/static/infoq/img/logo-121-75.yuij86g.png){kind=logo}
评论