1383. Maximum Performance of a Team
There are n engineers numbered from 1 to n and two arrays: speed and efficiency, where speed[i] and efficiency[i] represent the speed and efficiency for the i-th engineer respectively. Return the maximum performance of a team composed of at most k engineers, since the answer can be a huge number, return this modulo 10^9 + 7.
The performance of a team is the sum of their engineers’ speeds multiplied by the minimum efficiency among their engineers.
Example 1:
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2 Output: 60 Explanation: We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.
Example 2:
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3 Output: 68 Explanation: This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.
Example 3:
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4 Output: 72
Constraints:
1 <= n <= 10^5speed.length == nefficiency.length == n1 <= speed[i] <= 10^51 <= efficiency[i] <= 10^81 <= k <= n
给定n个工程师，每个工程师有自己的速度值speed和效率值efficiency，一个包含k个工程师的团队的总体performance等于所有工程师的速度之和乘以最小效率：sum(speed)*min(efficiency)。问最多选k个工程师，最大的performance是多少。
我一开始被“最多k个”迷惑了，一直以为是一个DP题，后来看题解发现不是。
由于performance=sum(speed)*min(efficiency)，所以首先对n个工程师按efficiency从大到小排序，然后对于前m个工程师，他们的最小efficiency就是当前遍历到的第m个工程师的efficiency。如果m已经超过k，则需要从m个工程师中剔除掉速度最小的工程师，因为此时的min(efficiency)固定是第m个工程师的efficiency，所以只需要剔除速度低的工程师。
那么，如果最优解是少于k个人，这种方法能否找到最优解呢？其实是可以的，因为对于每加入一个工程师，我们都会和当前最优解对比，刚开始的时候，队列中的人数肯定少于k。
完整代码如下：
class Solution {
public:
int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
vector<pair<int, int>> workers;
for (int i = 0; i < n; ++i) {
workers.push_back(make_pair(efficiency[i], speed[i]));
}
sort(workers.begin(), workers.end()); // 默认对pair.first升序排列
priority_queue <int, vector<int>, greater<int> > pq; // pq默认是最大堆，这是构建最小堆
long long ans = 0;
long long sum_speed = 0;
for (int i = n - 1; i >= 0; --i) {
sum_speed += workers[i].second;
pq.push(workers[i].second);
if (pq.size() > k) {
sum_speed -= pq.top();
pq.pop();
}
ans = max(ans, sum_speed*workers[i].first);
}
return ans % (int)(1e9 + 7);
}
};本代码提交AC，用时108MS。