2024-5-1——雇佣 K 位工人的总代价

本文主要是介绍2024-5-1——雇佣 K 位工人的总代价，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源

力扣每日一题；题序：2462

我的题解

方法一 优先队列

使用两个优先队列进行模拟
判断k是否等于costs的长度，若是则直接求costs的和返回就行了；否则判断candidates*2与sosts的长度的大小关系
若大于等于，则表示每次都在整个sosts上选择，只需要一个优先队列就行了；若小于，则需要两个优先队列，分别记录左侧和右侧。

时间复杂度：O((candidate+k)⋅log candidate)。
空间复杂度：O(candidate)

 public long totalCost(int[] costs, int k, int candidates) {int n=costs.length;if(k==n)return Arrays.stream(costs).asLongStream().sum();PriorityQueue<int[]> left=new PriorityQueue<>((a,b)->{if(a[0]==b[0]){return a[1]-b[1];}else{return a[0]-b[0];}});PriorityQueue<int[]> right=new PriorityQueue<>((a,b)->{if(a[0]==b[0]){return a[1]-b[1];}else{return a[0]-b[0];}});long res=0;if(candidates*2>=n){for(int i=0;i<n;i++){left.offer(new int[]{costs[i],i});}while(k>0){res+=left.poll()[0];k--;}}else{int lIndex=candidates;int rIndex=n-1-candidates;for(int i=0;i<candidates;i++){left.offer(new int[]{costs[i],i});right.offer(new int[]{costs[n-1-i],n-1-i});}while(k>0){//这里要注意左侧或右侧优先队列为空的情况int l=left.isEmpty()?Integer.MAX_VALUE:left.peek()[0];int r=right.isEmpty()?Integer.MAX_VALUE:right.peek()[0];if(l<=r){res+=left.poll()[0];if(lIndex<=rIndex){left.offer(new int[]{costs[lIndex++],lIndex-1});}}else{res+=right.poll()[0];if(lIndex<=rIndex){right.offer(new int[]{costs[rIndex--],rIndex+1});}}   k--;}}return res;}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~

这篇关于2024-5-1——雇佣 K 位工人的总代价的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---