题目描述
雇佣 K 名工人的最低成本
思路
参考官方题解和这里。
代码1（正确）
class Solution {
public:double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {int n = wage.size();double res = 0, totalq = 0; // totalqualityvector<int> h(n);for(int i = 0; i < n; i ++ ) h[i] = i;sort(h.begin(), h.end(), [&](int &a, int &b){return wage[a] * quality[b] < wage[b] * quality[a]; });for(int i = 0; i < n; i ++ ) cout << h[i] << ' ';cout << endl;priority_queue<int, vector<int>, less<int>> q; // 降序for(int i = 0; i < k - 1; i ++ ){q.push(quality[h[i]]);totalq += quality[h[i]];}for(int i = k - 1; i < n; i ++ ){q.push(quality[h[i]]);totalq += quality[h[i]];double cur = totalq / (double)quality[h[i]] * wage[h[i]];if(res == 0 || cur < res) res = cur;totalq -= q.top();q.pop();}return res;}
};
代码2（错误）
class Solution {
public:typedef pair<double, int> PDI;double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {int n = wage.size();double res = 0, totalq = 0; // totalqualityvector<int> h(n);for(int i = 0; i < n; i ++ ) h[i] = i;sort(h.begin(), h.end(), [&](int &a, int &b){return quality[a] < quality[b];});priority_queue<PDI, vector<PDI>, less<PDI>> q; // 降序for(int i = 0; i < k - 1; i ++ ){int idx = h[i];totalq += quality[idx];q.push({(double)wage[i] / quality[i],idx});}for(int i = k - 1; i < n; i ++ ){int idx = h[i];q.push({(double)wage[idx] / quality[idx],idx}); totalq += quality[idx];auto t = q.top();cout << totalq << ' ';double cur = totalq * t.first;if(res == 0 || cur < res) res = cur;totalq -= quality[t.second];q.pop();}return res;}
};
)
