2462.雇佣K位工人的总代价

链接：2462.雇佣K位工人的总代价
难度：Medium
标签：数组、双指针、模拟、堆（优先队列）
简介：返回雇佣恰好 k 位工人的总代价。

题解 1 - python

• 编辑时间：2024-05-01
• 执行用时：305ms
• 内存消耗：32.84MB
• 编程语言：python
• 解法介绍：优先队列。

class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
        n = len(costs)
        q = []
        for i in range(candidates): 
            heappush(q, (costs[i], i))
            if n - 1 - i >= candidates:
                heappush(q, (costs[n - 1 - i], n - 1 - i))
        l = candidates
        r = n - 1 - candidates
        res = 0
        while k:
            picked, picked_index = heappop(q)
            res += picked
            if l <= r:
                if picked_index < l:
                    heappush(q, (costs[l], l))
                    l += 1
                else:
                    heappush(q, (costs[r], r))
                    r -= 1
            k -= 1
        return res

题解 2 - cpp

• 编辑时间：2022-11-06
• 执行用时：136ms
• 内存消耗：75.2MB
• 编程语言：cpp
• 解法介绍：优先队列。

class Solution {
public:
    long long totalCost(vector<int>& costs, int k, int candidates) {
        int n = costs.size();
        int lmax = candidates, rmax = n - 1 - candidates;
        priority_queue<int, vector<int>, greater<int>> ql, qr, qa;
        for (int i = 0; i < candidates; i++) {
            ql.push(costs[i]);
            qr.push(costs[n - 1 - i]);
        }
        if (lmax > rmax) {
            for (int i = 0; i < n; i++) {
                qa.push(costs[i]);
            }
        }
        long long sum = 0;
        for (int i = 0; i < k; i++) {
            // cout << "i = " << i << endl;
            if (lmax > rmax) {
                sum += qa.top();
                qa.pop();
            } else {
                // cout << "lmax = " << lmax << ", rmax = " << rmax << endl;
                if (ql.top() <= qr.top()) {
                    sum += ql.top();
                    ql.pop();
                    ql.push(costs[lmax]);
                    lmax++;
                } else {
                    sum += qr.top();
                    qr.pop();
                    qr.push(costs[rmax]);
                    rmax--;
                }
                if (lmax > rmax) {
                    while (ql.size()) {
                        qa.push(ql.top());
                        ql.pop();
                    }
                    while (qr.size()) {
                        qa.push(qr.top());
                        qr.pop();
                    }
                }
                // cout << "lmax = " << lmax << ", rmax = " << rmax << endl;
            }
        }
        return sum;
    }
};