857. Minimum Cost to Hire K Workers

https://leetcode.com/problems/dungeon-game/description/

N个员工，每个员工有能力值和期望薪水，让选K个，满足按能力的比值发对应薪水，并且每个人薪水不能低于他的期待值。选K个，总花费为sum(quality_i) * max(wage_i / quaility_i)。一共有N种max(wage_i / quaility_i)，因此可以根据ratio排序后遍历。每次遍历到的元素即当前最大，要在它之前选k-1个使得sum(quality_j) 最小。找前K个quality最小的，用max heap (C++默认的priority_queue实现)。

/*
 * @lc app=leetcode id=857 lang=cpp
 *
 * [857] Minimum Cost to Hire K Workers
 */
class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int K) {
        const int N = quality.size();
        vector<vector<double>> workers;
        for (int i = 0; i < N; ++i) {
            workers.push_back({(double) (wage[i]) / quality[i], (double)quality[i]});
        } 
        sort(workers.begin(), workers.end(), [](vector<double> &a, vector<double> &b){
            return a[0] < b[0];
        });
        double res = DBL_MAX, qual_sum = 0;
        priority_queue<double> pq;
        for (const auto &worker : workers) {
            qual_sum += worker[1];
            pq.push(worker[1]);
            if (pq.size() > K) {
                qual_sum -= pq.top();
                pq.pop();
            }
            if (pq.size() == K) {
                res = min(res, qual_sum * worker[0]);
            }
        }
        return res;
    }
};