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

Arnab Chakraborty

更新于：2020年6月9日

214 次浏览

开启您的职业生涯

完成课程获得认证

开始学习