[每日一题] 2462.雇佣K位工人的总代价

博主： Richard
发布时间：2024 年 05 月 01 日
98 次浏览
暂无评论
1617字数
分类： LeetCode

> https://leetcode.cn/problems/total-cost-to-hire-k-workers/description/?envType=daily-question&envId=2024-05-01

从头尾两端找出最小代价的工人，每个工人只能使用一次，很容易想到维护两个小顶堆，这样每次取堆顶元素就好了。

如果 $candidates * 2 + k > n$ ，则表示所有工人都有可能被取到，因此此时只需要找出前 $k$ 个最小的元素相加即可。

```c++
class Solution {
public:
    long long totalCost(std::vector<int>& costs, int k, int candidates) {
        const int n = costs.size();

long long res = 0;
        int leftIndex = candidates, rightIndex = n - candidates - 1;

if (k + 2 * candidates > n) {
            std::nth_element(costs.begin(), costs.begin() + k, costs.end());
            return std::accumulate(costs.begin(), costs.begin() + k, 0LL);
        }
        
        std::priority_queue<int, std::vector<int>, std::greater<int>> left, right;
        for (int i = 0; i < candidates; ++i) {
            left.push(costs[i]);
            right.push(costs[n - i - 1]);
        }

int leftTop, rightTop;
        while (k--) {
            leftTop = left.top(), rightTop = right.top();
            if (leftTop > rightTop) {
                res += rightTop;
                right.pop();
                right.push(costs[rightIndex--]);
            } else {
                res += leftTop;
                left.pop();
                left.push(costs[leftIndex++]);
            }
        }
        
        return res;
    }
};
```

- 时间复杂度： $O((candidates + k) \cdot log \ candidates)$ 。

初始建堆需要 $O(candidates \cdot log \ candidates)$ 的时间，每一次雇佣工人都需要将新的工人入堆，消耗的时间为 $O(log \ candidates)$ ，总共需要雇佣 $k$ 次，因此总时间复杂度为 $O((candidates + k) \cdot log \ candidates)$ 。

- 空间复杂度：$O(candidates)$ 。

最后修改：2024 年 05 月 06 日