5359.最大的团队表现值 (Hard)*

题目描述*

公司有编号为 1 到 n 的 n 个工程师，给你两个数组 speed 和 efficiency ，其中 speed[i] 和 efficiency[i] 分别代表第 i 位工程师的速度和效率。请你返回由最多 k 个工程师组成的最大团队表现值，由于答案可能很大，请你返回结果对 10^9 + 7 取余后的结果。

团队表现值的定义为：一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。

提示*

1 <= n <= 10^5, speed.length == n, efficiency.length == n, 1 <= speed[i] <= 10^5, 1 <= efficiency[i] <= 10^8, 1 <= k <= n

代码*

先按照效率按降序排序，然后从左到右选择，这样每次的最小效率就是当前的效率。在左侧找到速度和最大的 k - 1 个，即维持一个 k - 1 大小的小顶堆。

使用优先队列实现小顶堆：

template<
    class T,
    class Container = std::vector<T>
    class Compare = std::less<typename Container::value_type>
 > class priority_queue;

堆排序

typedef long long ll;
class Solution {
public:
    int maxPerformance(int n, vector<int>& s, vector<int>& e, int k) {
        vector<int> order(n);
        for(int i = 0; i < n; i++) {
            order[i] = i;
        }
        // 按效率排序
        sort(order.begin(), order.end(), [&](int i, int j) {
            return e[i] > e[j];
        });
        priority_queue<int, vector<int>, greater<int>> pq;
        ll res = 0;
        ll sum = 0;
        for(int i = 0; i < n; i++) {
            pq.push(s[order[i]]);
            sum += s[order[i]];
            if(pq.size() > k) {
                sum -= pq.top();
                pq.pop();
            }
            res = max(res, sum * e[order[i]]);
        }
        return res % 1000000007;
    }
};

最后更新: July 23, 2022