题目描述

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

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

样例

输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
输出：60
解释：
我们选择工程师 2（speed=10 且 efficiency=4）和工程师 5（speed=5 且 efficiency=7）。
他们的团队表现值为 performance = (10 + 5) * min(4, 7) = 60 。

输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
输出：68
解释：
此示例与第一个示例相同，除了 k = 3 。
我们可以选择工程师 1 ，工程师 2 和工程师 5 得到最大的团队表现值。
表现值为 performance = (2 + 10 + 5) * min(5, 4, 7) = 68 。

输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
输出：72

限制

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

算法

(排序，堆) $O(n \log n)$

1. 首先将工程师按照效率从大到小排序。
2. 依次枚举每个工程师，维护一个大小为 $k$ 的小根堆，存放较大的 $k$ 个速度，同时用一个变量记录这 $k$ 个速度的和。
3. 对于枚举到的每个工程师，如果当前堆中元素不足 $k$ 个，则直接入堆，然后更新变量。如果已经等于了 $k$ 个，且堆顶小于当前工程师的速度，则堆顶出堆，当前工程师的速度入堆。
4. 枚举的每一次用速度总和乘当前的效率来更新答案。

时间复杂度

• 排序需要 $O(n \log n)$ 的时间。
• 每次枚举需要 $O(\log k)$ 的时间维护堆。
• 故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间来存放辅助顺序数组，以及存储小根堆。

C++ 代码

class Solution {
public:
    #define LL long long

    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        const int mod = 1000000007;
        vector<int> orders(n);
        for (int i = 0; i < n; i++)
            orders[i] = i;

        sort(orders.begin(), orders.end(), [&](int x, int y) {
            return efficiency[x] > efficiency[y]; 
        });

        priority_queue<int, vector<int>, greater<int>> q;
        LL tot = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            if (q.size() < k) {
                q.push(speed[orders[i]]);
                tot += speed[orders[i]];
            } else {
                if (q.top() < speed[orders[i]]) {
                    tot -= q.top();
                    q.pop();
                    q.push(speed[orders[i]]);
                    tot += speed[orders[i]];
                }
            }
            ans = max(ans, tot * efficiency[orders[i]]);
        }

        return ans % mod;
    }
};