C ++中团队的最高绩效
在这里,团队的绩效是工程师速度的总和乘以工程师中的最低效率。
因此,如果输入像n=6,速度=[1,5,8,2,10,3],效率=[9,7,2,5,4,3],k=2,则输出将是60,因为我们通过选择速度10和效率4的工程师以及速度5和效率7的工程师来拥有团队的最高绩效。也就是说,性能=(10+5)*min(4,7)=60。
为了解决这个问题,我们将遵循以下步骤-
ret:=0
定义一个2D数组v
对于初始化i:=0,当i<n时,更新(将i增加1),执行-
在v的末尾插入{e[i],s[i]}
以相反的顺序对数组v排序
定义一个优先级队列pq
和:=0
对于初始化i:=0,当i<n时,更新(将i增加1),执行-
sum:=sum的最高元素-pq
从pq中删除元素
如果pq的大小与k相同,则-
sum:=sum+v[i,1]
将v[i,1]插入pq
ret:=ret和和的最大值*v[i,0]
返回retmod(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