857. 雇佣 K 名工人的最低成本#
n 人の労働者がいます。quality と wage の 2 つの配列が与えられます。ここで、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;
}
};