数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++团队最大性能
假设有n名工程师，编号从1到n，我们还有两个数组：speed和efficiency，其中speed[i]和efficiency[i]分别代表第i位工程师的速度和效率。我们必须找到由最多k名工程师组成的团队的最大性能。答案可能非常大，因此返回它对10^9 + 7取模的结果。
这里，团队的性能是其工程师速度之和乘以其工程师中最低效率的结果。
因此，如果输入类似于n = 6，speed = [1,5,8,2,10,3]，efficiency = [9,7,2,5,4,3]，k = 2，则输出将为60，因为我们通过选择速度为10且效率为4的工程师以及速度为5且效率为7的工程师来获得团队的最大性能。也就是说，性能 = (10 + 5) * min(4, 7) = 60。
为了解决这个问题，我们将遵循以下步骤：
ret := 0
定义一个二维数组v
for 初始化 i := 0，当 i < n，更新（i 加 1），执行：
将 {e[i], s[i]} 插入到v的末尾
反向排序数组v
定义一个优先队列pq
sum := 0
for 初始化 i := 0，当 i < n，更新（i 加 1），执行：
如果pq的大小与k相同，则：
sum := sum - pq的顶部元素
从pq中删除元素
sum := sum + v[i, 1]
将v[i, 1]插入到pq中
ret := ret和sum * v[i, 0] 的最大值
返回 ret mod (1^9 + 7)
让我们看下面的实现来更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxPerformance(int n, vector<int>& s, vector<int>& e, int k){
long long int ret = 0;
vector<vector<int> > v;
for (int i = 0; i < n; i++) {
v.push_back({ e[i], s[i] });
}
sort(v.rbegin(), v.rend());
priority_queue<int, vector<int>, greater<int> > pq;
long long int sum = 0;
for (int i = 0; i < n; i++) {
if (pq.size() == k) {
sum -= pq.top();
pq.pop();
}
sum += v[i][1];
pq.push(v[i][1]);
ret = max(ret, sum * v[i][0]);
}
return ret % (long long int)(1e9 + 7);
}
};
main(){
Solution ob;
vector<int> v = {1,5,8,2,10,3};
vector<int> v1 = {9,7,2,5,4,3};
cout << (ob.maxPerformance(6,v,v1,2));
}输入
6, {1,5,8,2,10,3}, {9,7,2,5,4,3}, 2输出
60
更新于：2020年6月9日
214 次浏览
广告