第JavaC++題解leetcode857雇傭K名工人最低成本vectorpair目錄題目要求思路：優(yōu)先隊(duì)列+貪心JavaC++Rust

題目要求

思路：優(yōu)先隊(duì)列+貪心

Java

classSolution{

publicdoublemincostToHireWorkers(int[]quality,int[]wage,intk){

intn=quality.length;

double[][]ratio=newdouble[n][2];

for(inti=0;ii++){

ratio[i][0]=wage[i]*1.0/quality[i];

ratio[i][1]=quality[i]*1.0;

Arrays.sort(ratio,(a,b)-Dpare(a[0],b[0]));

PriorityQueueIntegerpq=newPriorityQueue((a,b)-b-a);

doubleres=1e18;

for(inti=0,tot=0;ii++){

intcur=(int)ratio[i][1];

tot+=cur;

pq.add(cur);

if(pq.size()k)

tot-=pq.poll();

if(pq.size()==k)

res=Math.min(res,tot*ratio[i][0]);

returnres;

時(shí)間復(fù)雜度：O(nlog?n)空間復(fù)雜度：O(n)

C++

學(xué)習(xí)了一下vector和pair的相互套用，以及自定義排序等內(nèi)容。

classSolution{

public:

doublemincostToHireWorkers(vectorintquality,vectorintwage,intk){

intn=quality.size();

vectorpairdouble,intratio;

for(inti=0;ii++){

ratio.emplace_back(wage[i]*1.0/quality[i],quality[i]);

sort(ratio.begin(),ratio.end(),[](constpairdouble,inta,constpairdouble,intb){

returna.firstb.first;

priority_queueint

doubleres=1e18;

for(inti=0,tot=0;ii++){

intcur=ratio[i].second;

tot+=cur;

pq.emplace(cur);

if(pq.size()k){

tot-=pq.top();

pq.pop();

if(pq.size()==k)

res=min(res,tot*ratio[i].first);

returnres;

時(shí)間復(fù)雜度：O(nlog?n)空間復(fù)雜度：O(n)

Rust

usestd::collections::BinaryHeap;

implSolution{

pubfnmincost_to_hire_workers(quality:Veci32,wage:Veci32,k:i32)-f64{

let(mutres,muttot,mutpq)=(f64::MAX,0,BinaryHeap::new());

letmutratio=quality.iter().zip(wage.iter()).map(|(q,w)|(*wasf64/*qasf64,*qasf64)).collect::Vec_();

ratio.sort_by(|a,b|a.0.partial_cmp(b.0).unwrap());

for(a,b)inratio{

tot+=basi32;

pq.push(basi32);

ifpq.len()asi32k{

tot-=pq.pop().unwrap();

ifpq.len()asi32==k{

res=res.min(a*totasf64);

時(shí)間復(fù)雜度：O(n