## 857. Minimum Cost to Hire K Workers

There are `N`

workers. The `i`

-th worker has a `quality[i]`

and a minimum wage expectation `wage[i]`

.

Now we want to hire exactly `K`

workers to form a *paid group*. When hiring a group of K workers, we must pay them according to the following rules:

- Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
- Every worker in the paid group must be paid at least their minimum wage expectation.

Return the least amount of money needed to form a paid group satisfying the above conditions.

**Example 1:**

Input:quality = [10,20,5], wage = [70,50,30], K = 2Output:105.00000Explanation: We pay 70 to 0-th worker and 35 to 2-th worker.

**Example 2:**

Input:quality = [3,1,10,10,1], wage = [4,8,2,2,7], K = 3Output:30.66667Explanation: We pay 4 to 0-th worker, 13.33333 to 2-th and 3-th workers seperately.

**Note:**

`1 <= K <= N <= 10000`

, where`N = quality.length = wage.length`

`1 <= quality[i] <= 10000`

`1 <= wage[i] <= 10000`

- Answers within
`10^-5`

of the correct answer will be considered correct.

## Rust Solution

```
struct Solution;
use std::collections::BinaryHeap;
impl Solution {
fn mincost_to_hire_workers(quality: Vec<i32>, wage: Vec<i32>, k: i32) -> f64 {
let k = k as usize;
let n = quality.len();
let mut workers: Vec<usize> = (0..n).collect();
let rate: Vec<f64> = (0..n).map(|i| wage[i] as f64 / quality[i] as f64).collect();
workers.sort_by(|&i, &j| rate[i].partial_cmp(&rate[j]).unwrap());
let mut res = std::f64::MAX;
let mut queue: BinaryHeap<i32> = BinaryHeap::new();
let mut sum = 0;
for i in workers {
let r = rate[i];
let q = quality[i];
queue.push(q);
sum += q;
if queue.len() > k {
sum -= queue.pop().unwrap();
}
if queue.len() == k {
res = res.min(r * sum as f64);
}
}
res
}
}
#[test]
fn test() {
use assert_approx_eq::assert_approx_eq;
let quality = vec![10, 20, 5];
let wage = vec![70, 50, 30];
let k = 2;
let res = 105.00000;
assert_approx_eq!(Solution::mincost_to_hire_workers(quality, wage, k), res);
let quality = vec![3, 1, 10, 10, 1];
let wage = vec![4, 8, 2, 2, 7];
let k = 3;
let res = 30.666667;
assert_approx_eq!(Solution::mincost_to_hire_workers(quality, wage, k), res);
}
```

Having problems with this solution? Click here to submit an issue on github.