857. 雇佣 K 名工人的最低成本#
有 n 名工人。 给定兩個數組 quality 和 wage ，其中，quality[i] 表示第 i 名工人的工作質量，其最低期望工資為 wage[i] 。
現在我們想雇佣 k 名工人組成一個 * 工資組。* 在雇佣 一組 k 名工人時，我們必須按照下述規則向他們支付工資：
- 對工資組中的每名工人，應當按其工作質量與同組其他工人的工作質量的比例來支付工資。
- 工資組中的每名工人至少應當得到他們的最低期望工資。
給定整數 k ，返回 組成滿足上述條件的付費群體所需的最小金額 。在實際答案的 以內的答案將被接受。
示例 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。
提示：
優先佇列#
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;
}
};