Java C++ 题解leetcode857雇佣K名工人最低成本vector pair

题目描述：

给定两个长度为N的整数数组，W数组表示每个工人的工资，Q数组表示每个工人完成工作的质量。
现在要雇佣K名工人去完成一些工作，每个工人只能完成一项工作，工人完成一项工作的质量就是该工作质量的总和，而这些工作的总成本是所有工人的工资总和。
求最小的总成本。

思路分析：

先将工资按比例排序，使用最小堆，维护当前最小的K个工资，同时记录下当前最小K个工资的序号，计算每个工人的价格，返回最小值即可。

代码实现：

class Worker
{
public:
    int quality;
    int wage;
    double ratio;
    Worker(int q, int w) : quality(q), wage(w), ratio(double(w) / double(q)){}
    bool operator<(const Worker& a)const
    {
        return ratio < a.ratio;
    }
};

class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int K) {
        vector<Worker>workers;
        int n = quality.size();
        for (int i = 0; i < n; i++) {
            workers.push_back(Worker(quality[i], wage[i]));
        }
        sort(workers.begin(), workers.end());
        priority_queue<int>pq;
        double res = DBL_MAX;
        int work_quality = 0;
        for (auto worker : workers) {
            int q = worker.quality;
            int w = worker.wage;
            double r = worker.ratio;
            pq.push(q);
            work_quality += q;
            if (pq.size() > K) {
                int dq = pq.top();
                pq.pop();
                work_quality -= dq;
            }
            if (pq.size() == K) {
                res = min(res, work_quality * r);
            }
        }
        return res;
    }
};

示例1：

输入:

quality = [10,20,5], wage = [70,50,30], K = 2

输出:

105

解释:

雇用第一名工人完成质量为10的工作，并支付 70$。雇用第二名工人完成质量为20的工作，并支付 50$。

示例2：

输入:

quality = [3,1,10,10,1], wage = [4,8,2,2,7], K = 3

输出:

30.66667

解释:

雇用第一名工人完成质量为3的工作，并支付 4$。雇用第二名工人完成质量为7的工作，并支付 7$。雇用第三名工人完成质量为10的工作，并支付 19.33333$。