857

class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
        vector<pair<double, int>> workers;
        int n = quality.size();

        // Calculate the wage/qual ratio for each worker and sort them as per ratio.
        for(int i=0; i<n; i++)
            workers.push_back({double(wage[i])/quality[i], quality[i]});
        sort(workers.begin(), workers.end());

        // Pick k min quality workers and pay as per highest ratio seen so far.
        priority_queue<int> pq;
        double qsum = 0, ans = DBL_MAX;
        for(auto worker: workers){
            qsum += worker.second;
            pq.push(worker.second);
            if(pq.size() > k){
                qsum -= pq.top();
                pq.pop();
            }
            if(pq.size() == k)
                ans = min(ans, qsum*worker.first);
        }
        return ans;
    }
};