[每日一题] 857.雇佣K名工人的最低成本

Richard

2024 年 05 月 03 日

121 次浏览

暂无评论

1855字数

LeetCode

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

根据题目条件分析如下：

- 必定有至少一个工人 $c$ 的工资为最低期望工资；
- 令  $r_i = \frac{wage[i]}{quality[i]}$ ，则每个人的工资 $cost[i] = quality[i] \times r_c$ 。
- 需要保证每个人的工资大于等于其最低期望工资，即 $cost[i] \geq wage[i]$ 。 易知 $wage[i] = quality[i] \times r_i$ ，所以 $r_i \leq r_c$ 时，发给工人 $i$ 的工资是一定大于其最低期望工资的。因此只需要按照 $r_i$ 排序，就可以快速地找出哪些工人是可选的。
- 题目要求求最低的总工资，易知总工资 $S = \sum cost[i] = Q \times r_c$ ，其中 $Q$ 为选中的工人的工作质量和。因此在枚举 $r_c$ 的时候，还需要维护一个大顶堆，用于记录使得 $Q$ 最小的 $k$ 个工人。

```c++
class Solution {
public:
    double mincostToHireWorkers(std::vector<int>& quality, std::vector<int>& wage, int k) {
        const int n = quality.size();

std::vector<int> ids(n);
        std::iota(ids.begin(), ids.end(), 0);
        std::sort(ids.begin(), ids.end(), [&] (const int &i, const int &j) {
            return wage[i] * quality[j] < wage[j] * quality[i];
        });

int Q = 0;
        std::priority_queue<int> chosen;
        for (int i = 0; i < k; ++i) {
            chosen.push(quality[ids[i]]);
            Q += quality[ids[i]];
        }

int curQuality;
        double S = (double)wage[ids[k - 1]] / (double)quality[ids[k - 1]] * (double)Q;
        for (int i = k; i < n; ++i) {
            curQuality = quality[ids[i]];
            if (curQuality < chosen.top()) {
                Q = Q - chosen.top() + curQuality;
                chosen.pop();
                chosen.push(curQuality);
                S = std::min(S, (double)wage[ids[i]] / (double)curQuality * (double)Q);
            }
        }

return S;
    }
};
```

- 时间复杂度：$O(nlogn)$ 。排序所需要的时间为 $O(nlogn)$ ，建堆和维护堆的时间为 $O(nlogk)$ 。题目中给出了 $k \leq n$ ，所以最终时间复杂度为 $O(nlogn)$ 。
- 空间复杂度：$O(n)$ ，需要一个数组来存储按 $r_i$ 排序后的结果。由于 $k \leq n$ ，所以建堆所需的 $O(logk)$ 复杂度可以省略，最终空间复杂度为 $O(n)$ 。

最后修改：2024 年 05 月 03 日