class Solution {
typedef pair<int, int> PII;
public:
double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
int n = quality.size();
vector<PII> person;
for(int i = 0; i < n; ++i) {
person.emplace_back(wage[i], quality[i]);
}
sort(person.begin(), person.end(), [](PII& p1, PII& p2) {
return double(p1.first) / p1.second < double(p2.first) / p2.second;
});
priority_queue<int> pqQuality;
double ret = 1e20;
double qualities = 0;
for(auto [w, q]: person) { // wage, quality
qualities += q;
pqQuality.push(q);
if(pqQuality.size() > k) {
qualities -= pqQuality.top();
pqQuality.pop();
}
if(pqQuality.size() == k) {
ret = min(ret, double(w) / q * qualities);
}
}
return ret;
}
};
// wage / quality = constant, hire the one with the minimum ratio first
// the per quality wage should be the same
// sort based on per quality wage(increasing), traverse and use the least quality ones(working hour)
// per quality wage increases, but the working hour may be reduced find the optimum
// the mincost = (per quality wage) * (working hours)
