Skip to content

Commit dcaf658

Browse files
yanglbmeyanglbme
authored
feat: add solutions to lc problems: No.2462,2798 (doocs#2679)
1 parent 23f7050 commit dcaf658

File tree

12 files changed

+405
-344
lines changed

12 files changed

+405
-344
lines changed

‎solution/2400-2499/2462.Total Cost to Hire K Workers/README.md

Lines changed: 130 additions & 97 deletions
Original file line numberDiff line numberDiff line change
@@ -64,78 +64,77 @@
6464

6565
### 方法一：优先队列（小根堆）
6666

67-
我们用一个优先队列（小根堆）维护当前的候选工人，用变量 $i$ 和 $j$ 标记最前面工人的最大小标和最后面工人的最小下标。初始时 $i = candidates - 1$，而 $j = n - candidates$。
67+
我们首先判断 $candidates \times 2$ 是否大于等于 $n$，如果是，我们直接返回前 $k$ 个最小的工人的代价之和。
6868

69-
我们先将前面 $candidates$ 个工人的代价放入优先队列中，再将最后面 $candidates$ 个工人的代价放入优先队列中，放入之前需要判断根据 $i$ 或 $j$ 是否已经在优先队列中，如果已经在优先队列中，则不需要再放入。
69+
否则，我们使用一个小根堆 $pq$ 来维护前 $candidates$ 个工人和后 $candidates$ 个工人的代价。
7070

71-
循环 $k$ 次，每次从优先队列中取出最小代价的工人，累加代价。如果当前取出的工人下标 $x$ 在最前面工人的下标范围 $[0,..i]$ 中，则将 $i$ 向右移动一位，然后判断是否要将 $i$ 对应的工人代价放入优先队列中；如果取出的下标在最后面工人的下标范围 $[j,..n-1]$ 中，则将 $j$ 向左移动一位，然后判断是否要将 $j$ 对应的工人代价放入优先队列中。
71+
我们首先将前 $candidates$ 个工人的代价以及对应的下标加入小根堆 $pq$ 中，然后将后 $candidates$ 个工人的代价以及对应的下标加入小根堆 $pq$ 中。用两个指针 $l$ 和 $r$ 分别指向前后待选工人的下标，初始时 $l = candidates$, $r = n - candidates - 1$。
7272

73-
遍历结束后，将累加的代价作为答案返回。
73+
然后我们进行 $k$ 次循环，每次从小根堆 $pq$ 中取出代价最小的工人，将其代价加入答案，如果 $l > r$，说明前后待选工人已经全部被选完，直接跳过。否则，如果当前工人的下标小于 $l$，说明是前面的工人，我们将第 $l$ 个工人的代价以及下标加入小根堆 $pq$ 中，然后 $l$ 加一；否则，我们将第 $r$ 个工人的代价以及下标加入小根堆 $pq$ 中，然后 $r$ 减一。
7474

75-
时间复杂度 $O(n\times \log n)$。其中 $n$ 为数组 $costs$ 的长度。
75+
循环结束后，返回答案即可。
76+
77+
时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 $costs$ 的长度。
7678

7779
<!-- tabs:start -->
7880

7981
```python
8082
class Solution:
8183
def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
82-
q = []
8384
n = len(costs)
84-
i, j = candidates - 1, n - candidates
85-
for h in range(candidates):
86-
q.append((costs[h], h))
87-
for h in range(n - candidates, n):
88-
if h > i:
89-
q.append((costs[h], h))
90-
heapify(q)
85+
if candidates * 2 >= n:
86+
return sum(sorted(costs)[:k])
87+
pq = []
88+
for i, c in enumerate(costs[:candidates]):
89+
heappush(pq, (c, i))
90+
for i in range(n - candidates, n):
91+
heappush(pq, (costs[i], i))
92+
heapify(pq)
93+
l, r = candidates, n - candidates - 1
9194
ans = 0
9295
for _ in range(k):
93-
c, x = heappop(q)
96+
c, i = heappop(pq)
9497
ans += c
95-
if x <= i:
96-
i += 1
97-
if i < j:
98-
heappush(q, (costs[i], i))
99-
if x >= j:
100-
j -= 1
101-
if i < j:
102-
heappush(q, (costs[j], j))
98+
if l > r:
99+
continue
100+
if i < l:
101+
heappush(pq, (costs[l], l))
102+
l += 1
103+
else:
104+
heappush(pq, (costs[r], r))
105+
r -= 1
103106
return ans
104107
```
105108

106109
```java
107110
class Solution {
108111
public long totalCost(int[] costs, int k, int candidates) {
109-
PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> {
110-
if (a[0] == b[0]) {
111-
return a[1] - b[1];
112-
}
113-
return a[0] - b[0];
114-
});
115112
int n = costs.length;
116-
int i = candidates - 1, j = n - candidates;
117-
for (int h = 0; h < candidates; ++h) {
118-
q.offer(new int[] {costs[h], h});
119-
}
120-
for (int h = n - candidates; h < n; ++h) {
121-
if (h > i) {
122-
q.offer(new int[] {costs[h], h});
113+
long ans = 0;
114+
if (candidates * 2 >= n) {
115+
Arrays.sort(costs);
116+
for (int i = 0; i < k; ++i) {
117+
ans += costs[i];
123118
}
119+
return ans;
124120
}
125-
long ans = 0;
121+
PriorityQueue<int[]> pq
122+
= new PriorityQueue<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
123+
for (int i = 0; i < candidates; ++i) {
124+
pq.offer(new int[] {costs[i], i});
125+
pq.offer(new int[] {costs[n - i - 1], n - i - 1});
126+
}
127+
int l = candidates, r = n - candidates - 1;
126128
while (k-- > 0) {
127-
var e = q.poll();
128-
int c = e[0], x = e[1];
129-
ans += c;
130-
if (x <= i) {
131-
if (++i < j) {
132-
q.offer(new int[] {costs[i], i});
133-
}
129+
var p = pq.poll();
130+
ans += p[0];
131+
if (l > r) {
132+
continue;
134133
}
135-
if (x >= j) {
136-
if (--j > i) {
137-
q.offer(new int[] {costs[j], j});
138-
}
134+
if (p[1] < l) {
135+
pq.offer(new int[] {costs[l], l++});
136+
} else {
137+
pq.offer(new int[] {costs[r], r--});
139138
}
140139
}
141140
return ans;
@@ -144,31 +143,33 @@ class Solution {
144143
```
145144

146145
```cpp
147-
using pii = pair<int, int>;
148-
149146
class Solution {
150147
public:
151148
long long totalCost(vector<int>& costs, int k, int candidates) {
152-
priority_queue<pii, vector<pii>, greater<pii>> q;
153149
int n = costs.size();
154-
int i = candidates - 1, j = n - candidates;
155-
for (int h = 0; h < candidates; ++h) q.push({costs[h], h});
156-
for (int h = n - candidates; h < n; ++h)
157-
if (h > i) q.push({costs[h], h});
150+
if (candidates * 2 > n) {
151+
sort(costs.begin(), costs.end());
152+
return accumulate(costs.begin(), costs.begin() + k, 0LL);
153+
}
154+
using pii = pair<int, int>;
155+
priority_queue<pii, vector<pii>, greater<pii>> pq;
156+
for (int i = 0; i < candidates; ++i) {
157+
pq.emplace(costs[i], i);
158+
pq.emplace(costs[n - i - 1], n - i - 1);
159+
}
158160
long long ans = 0;
161+
int l = candidates, r = n - candidates - 1;
159162
while (k--) {
160-
auto [c, x] = q.top();
161-
q.pop();
162-
ans += c;
163-
if (x <= i) {
164-
if (++i < j) {
165-
q.push({costs[i], i});
166-
}
163+
auto [cost, i] = pq.top();
164+
pq.pop();
165+
ans += cost;
166+
if (l > r) {
167+
continue;
167168
}
168-
if (x >= j) {
169-
if (--j > i) {
170-
q.push({costs[j], j});
171-
}
169+
if (i < l) {
170+
pq.emplace(costs[l], l++);
171+
} else {
172+
pq.emplace(costs[r], r--);
172173
}
173174
}
174175
return ans;
@@ -177,48 +178,80 @@ public:
177178
```
178179
179180
```go
180-
func totalCost(costs []int, k int, candidates int) int64 {
181-
q := hp{}
181+
func totalCost(costs []int, k int, candidates int) (ans int64) {
182182
n := len(costs)
183-
i, j := candidates-1, n-candidates
184-
for h := 0; h < candidates; h++ {
185-
heap.Push(&q, pair{costs[h], h})
186-
}
187-
for h := n - candidates; h < n; h++ {
188-
if h > i {
189-
heap.Push(&q, pair{costs[h], h})
183+
if candidates*2 > n {
184+
sort.Ints(costs)
185+
for _, x := range costs[:k] {
186+
ans += int64(x)
190187
}
188+
return
191189
}
192-
ans := 0
193-
for k > 0 {
194-
p := heap.Pop(&q).(pair)
195-
c, x := p.c, p.x
196-
ans += c
197-
if x <= i {
198-
i++
199-
if i < j {
200-
heap.Push(&q, pair{costs[i], i})
201-
}
190+
pq := hp{}
191+
for i, x := range costs[:candidates] {
192+
heap.Push(&pq, pair{x, i})
193+
heap.Push(&pq, pair{costs[n-i-1], n - i - 1})
194+
}
195+
l, r := candidates, n-candidates-1
196+
for ; k > 0; k-- {
197+
p := heap.Pop(&pq).(pair)
198+
ans += int64(p.cost)
199+
if l > r {
200+
continue
202201
}
203-
if x >= j {
204-
j--
205-
if i < j {
206-
heap.Push(&q, pair{costs[j], j})
207-
}
202+
if p.i < l {
203+
heap.Push(&pq, pair{costs[l], l})
204+
l++
205+
} else {
206+
heap.Push(&pq, pair{costs[r], r})
207+
r--
208208
}
209-
k--
210209
}
211-
return int64(ans)
210+
return
212211
}
213212
214-
type pair struct{ c, x int }
213+
type pair struct{ cost, i int }
215214
type hp []pair
216215
217-
func (h hp) Len() int { return len(h) }
218-
func (h hp) Less(i, j int) bool { return h[i].c < h[j].c || h[i].c == h[j].c && h[i].x < h[j].x }
219-
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
220-
func (h *hp) Push(v any) { *h = append(*h, v.(pair)) }
221-
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
216+
func (h hp) Len() int { return len(h) }
217+
func (h hp) Less(i, j int) bool {
218+
return h[i].cost < h[j].cost || (h[i].cost == h[j].cost && h[i].i < h[j].i)
219+
}
220+
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
221+
func (h *hp) Push(v any) { *h = append(*h, v.(pair)) }
222+
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
223+
```
224+
225+
```ts
226+
function totalCost(costs: number[], k: number, candidates: number): number {
227+
const n = costs.length;
228+
if (candidates * 2 >= n) {
229+
costs.sort((a, b) => a - b);
230+
return costs.slice(0, k).reduce((acc, x) => acc + x, 0);
231+
}
232+
const pq = new PriorityQueue({
233+
compare: (a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]),
234+
});
235+
for (let i = 0; i < candidates; ++i) {
236+
pq.enqueue([costs[i], i]);
237+
pq.enqueue([costs[n - i - 1], n - i - 1]);
238+
}
239+
let [l, r] = [candidates, n - candidates - 1];
240+
let ans = 0;
241+
while (k--) {
242+
const [cost, i] = pq.dequeue()!;
243+
ans += cost;
244+
if (l > r) {
245+
continue;
246+
}
247+
if (i < l) {
248+
pq.enqueue([costs[l], l++]);
249+
} else {
250+
pq.enqueue([costs[r], r--]);
251+
}
252+
}
253+
return ans;
254+
}
222255
```
223256

224257
<!-- tabs:end -->

0 commit comments

Comments
 (0)