[LeetCode]Minimum Cost to Hire K Workers

题目链接

这道题要求两点：

1. 所有人按照quality等比例支付工资
2. 所有人必须满足最低薪酬

所以对于一个K个人的group，这K个人的总工资是取决于两项的：

1. K个人当中，wage/quality的比例最高的
2. K个人的总quality

那么我们可以对所有人按照wage/quality的比例从小到大排序。并且维护一个根据quality比较的max heap。这样当我们遍历到第i个人，他的wage/quality是目前为止最高的，所以其为决定整体工资的第一个因素(后面的元素我们不需要考虑，因为其wage/quality比例更大，放进去当前元素就无法决定最大比例了)。在这个条件下，如果heap中元素大于K个，我们把quality最高的踢掉一直到size为K，这样第二个因素可以控制到最小，那么两者相乘就是当前wage/quality比例下的K个人的最少工资。那么我们遍历完这所有的wage/quality比例，在所有最少工资中取最小的即可。时间复杂度O(N * log N)，代码如下：

	class Solution {
	public:
	double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int K) {
	int len = quality.size();
	vector<int> idxs;
	for (int i = 0; i < len; ++i)idxs.push_back(i);
	auto comp = [&](const int& lhs, const int& rhs)
	{
	return getRatio(quality[lhs], wage[lhs]) < getRatio(quality[rhs], wage[rhs]);
	};
	sort(idxs.begin(), idxs.end(), comp);
	//find the lowest total quality for current ratio
	//we alwasy pick the largest ratio as the ratio
	//of current group since we need to meet the minimum
	//wage request for everyone
	priority_queue<int> pq;
	double res = 10e9;
	int totalQ = 0;
	for (const auto& idx : idxs)
	{
	double ratio = getRatio(quality[idx], wage[idx]);
	int currQ = quality[idx];
	if (pq.size() == K)
	{
	totalQ -= pq.top();
	pq.pop();
	}
	//bug: pop first then push, otherwise new pushed element might be popped out
	totalQ += currQ;
	pq.push(currQ);
	if (pq.size() == K)res = min(res, totalQ * ratio);
	}
	return res;
	}
	private:
	double getRatio(int q, int w)
	{
	return static_cast<double>(w) / static_cast<double>(q);
	}
	};

view raw Minimum Cost to Hire K Workers.cpp hosted with ❤ by GitHub