### 857. Minimum Cost to Hire K Workers#

There are `n`

workers. Given two arrays `quality`

and `wage`

, where `quality[i]`

represents the work quality of the i-th worker and `wage[i]`

represents the minimum expected wage for that worker.

Now, we want to hire `k`

workers to form a *wage group*. When hiring a group of `k`

workers, we must pay them wages according to the following rules:

- For each worker in the wage group, the wage should be paid in proportion to their work quality compared to the work quality of other workers in the same group.
- Each worker in the wage group should receive at least their minimum expected wage.

Given an integer `k`

, return the *minimum amount of money needed to form a wage group that satisfies the above conditions*. Answers within $10^{-5}$ of the actual answer will be accepted.

**Example 1:**

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

**Example 2:**

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

**Note:**

- $n == quality.length == wage.length$
- $1 \leq k \leq n \leq 10^4$
- $1 \leq quality[i], wage[i] \leq 10^4$

### Priority Queue#

```
class Solution {
public:
double mincostToHireWorkers(vector<int> &quality, vector<int> &wage, int k) {
int n = quality.size();
vector<int> h(n, 0);
iota(h.begin(), h.end(), 0);
sort(h.begin(), h.end(), [&](const int &a, const int &b) {
return quality[a] * wage[b] > quality[b] * wage[a];
});
double res = 1e9;
double totalq = 0.0;
priority_queue<int, vector<int>, less<int>> q;
for (int i = 0; i < k - 1; ++i) {
totalq += quality[h[i]];
q.push(quality[h[i]]);
}
for (int i = k - 1; i < n; ++i) {
int idx = h[i];
totalq += quality[idx];
q.push(quality[idx]);
double totalc = ((double)wage[idx] / quality[idx]) * totalq;
res = min(res, totalc);
totalq -= q.top();
q.pop();
}
return res;
}
};
```