R: [閒聊] 每日LeetCode已回收
https://leetcode.com/problems/total-cost-to-hire-k-workers/description/
2462. Total Cost to Hire K Workers
給你一個陣列costs，costs[i] 表示第 i 個應徵者的期望薪資，我們要開一個會議
每次從最左邊和最右的應徵者開始挑選 candidates 個人，並從中雇用最便宜的應徵
者（成本相同的話靠左的人優先），剩下的人進入下一輪會議，公司需要挑選出 k 個人，求出雇用的最小成本。
Example 1:
Input: costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
Output: 11
Explanation: We hire 3 workers in total. The total cost is initially 0.
- In the first hiring round we choose the worker from
[17,12,10,2,7,2,11,20,8]. The lowest cost is 2, and we break the tie by the
smallest index, which is 3. The total cost = 0 + 2 = 2.
- In the second hiring round we choose the worker from
[17,12,10,7,2,11,20,8]. The lowest cost is 2 (index 4). The total cost = 2 +
2 = 4.
- In the third hiring round we choose the worker from [17,12,10,7,11,20,8].
The lowest cost is 7 (index 3). The total cost = 4 + 7 = 11. Notice that the
worker with index 3 was common in the first and last four workers.
The total hiring cost is 11.
思路：
1.照題目需求，每次都從最左邊和最右邊挑選 candidates 個人並放進 Min Heap 裡
按 costs 排序，相同就比較索引，這樣每次拿出來的就會是最優解，如果取了左邊的
人那下次就要先從左邊補人，右邊反之。
（原始的解法太醜了我就不貼了）
2.上面是比較直觀的解，還可以做一些優化，開頭可以直接判斷 candidates 是否可以
直接包含全部 costs，這樣只要直接排序後取 k 個就是最佳解，不必一直維護heap。
3.可以用兩個 Heap 來保存左半邊和右半邊，左半邊的 Heap 優先取出，可以免除一些
繁瑣的判斷。
Java Code：
---------------------------------------------
class Solution {
public long totalCost(int[] costs, int k, int candidates) {
int n = costs.length;
long res = 0;
if (2 * candidates > n - k || n == k) {
Arrays.sort(costs);
for (int i = 0; i < k; i++) {
res += costs[i];
}
return res;
}
PriorityQueue<Integer> left = new PriorityQueue<>();
PriorityQueue<Integer> right = new PriorityQueue<>();
int l = 0;
int r = n - 1;
for (int i = 0; i < candidates; i++) {
left.add(costs[l++]);
right.add(costs[r--]);
}
while (k-- > 0) {
if (left.peek() <= right.peek()) {
res += left.poll();
left.add(costs[l++]);
} else {
res += right.poll();
right.add(costs[r--]);
}
}
return res;
}
}
---------------------------------------------
--
https://i.imgur.com/YPBHGGE.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1687799850.A.AF9.html
※ 編輯: Rushia (122.100.75.86 臺灣), 06/27/2023 01:22:31
討論串 (同標題文章)
完整討論串 (本文為第 355 之 719 篇)：