857. Minimum Cost to Hire K Workers.cpp

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

        vector<pair<double, int>> worker_ratio(n);
        for (int worker = 0; worker < n; worker++) {
            worker_ratio[worker] = make_pair(
                (double)wage[worker] / quality[worker], quality[worker]);
        }
        sort(begin(worker_ratio), end(worker_ratio));

        priority_queue<int, vector<int>> pq;

        double sum_quality = 0;
        for (int i = 0; i < k; i++) {
            pq.push(worker_ratio[i].second);
            sum_quality += worker_ratio[i].second;
        }

        double managerRatio = worker_ratio[k - 1].first;
        double result = managerRatio * sum_quality;

        for (int manager = k; manager < n; manager++) {

            managerRatio = worker_ratio[manager].first;

            pq.push(worker_ratio[manager].second);
            sum_quality += worker_ratio[manager].second;

            if (pq.size() > k) {
                sum_quality -= pq.top();
                pq.pop();
            }

            result = min(result, managerRatio * sum_quality);
        }

        return result;
    }
};