- 科技
- leetcode 857 (堆)
bool cmp( vector
<double> &a
,vector
<double> &b
){
return a
[0]<b
[0];
}
bool cmp1( vector
<double> &a
, vector
<double> &b
){
return a
[1]<b
[1];
}
class Solution{
public:
double mincostToHireWorkers(vector
<int>&quality
,vector
<int>&wage
,int K
){
vector
<vector
<double>> worker(quality
.size(),{0.0,0.0});
for(int i
=0;i
<quality
.size();i
++){
worker
[i
][0]=wage
[i
]/(double)quality
[i
];
worker
[i
][1]=quality
[i
];
}
sort(worker
.begin(),worker
.end(),cmp
);
double res
;
priority_queue
<double,vector
<double>,less
<int>>q
;
double qual
=0.0;
for(int i
=0;i
<worker
.size();i
++){
q
.push(worker
[i
][1]);
qual
+=worker
[i
][1];
if(q
.size()==K
) res
=qual
*worker
[i
][0];
if(q
.size()>K
){
qual
-=q
.top();
q
.pop();
res
=min(res
,qual
*worker
[i
][0]);
}
}
return res
;
}
};
Processed:
0.021, SQL:
8
