LeetCode.857.Minimum.Cost.to.Hire.K.Workers

LeetCode 857. Minimum Cost to Hire K Workers

Desc:

N个worker,每个worker有quality和wage,你需要雇佣K个worker,这K个worker之间的real wage比例和quality比例相同,且real wage不小于wage。

答案允许有10^-5的误差

My_Ans:

冷静分析,首先 worker之间严格按照比例发real wage 且

定义

假设已经选出了K个worker,那么这个standard worker就需要设置为ratio最大的那个worker

否则会有worker的real wage<wage。

因此对于每个standard worker 我们需要找出k-1个ratio小于它的worker,而且K个worker的

按照ratio对worker从小到大排序,枚举第i个worker作为standard worker

所以第0~第i-1个worker均为满足ratio满足要求的,然后需要找出K-1个quality最小的即可

考虑维护一个最多K个元素的单调队列 队首的worker的quality最大 队列中均满足ratio小于当前standard worker

每次standard worker后移 将当前的standard worker的quality和队首quality进行比较,

如果当前standard worker的quality小于队首quality 弹出队首 插入当前standard worker

并且维护一个Sum记录当前queue里的quality之和

不断更新最小值即可

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int K) {
double ans=0x3f3f3f3f;
vector<pair<double,int>>rate;
for(int i=0;i<quality.size();i++)
rate.push_back(make_pair(1.0*wage[i]/quality[i],i));
sort(rate.begin(),rate.end());
priority_queue<int>que;
int sum=0;
for(int i=0;i<rate.size();i++)
{
if(que.size()<K-1){
que.push(quality[rate[i].second]);
sum+=quality[rate[i].second];
}
else{
ans=min(ans,1.0*rate[i].first*(sum+quality[rate[i].second]));
if(!que.empty()&&que.top()>quality[rate[i].second]){
int tmp=que.top();
que.push(quality[rate[i].second]);
que.pop();
sum=sum-tmp+quality[rate[i].second];
}
}
}
return ans;
}
};