C++에서 팀의 최대 성능

n명의 엔지니어가 있다고 가정합니다. 그것들은 1에서 n까지 번호가 매겨져 있으며 우리는 또한 속도와 효율성의 두 가지 배열을 가지고 있습니다. 여기에서 속도[i]와 효율성[i]은 i번째 엔지니어의 속도와 효율성을 나타냅니다. 최대 k명의 엔지니어로 구성된 팀의 최대 성능을 찾아야 합니다. 답은 매우 클 수 있으므로 모듈로 10^9 + 7을 반환합니다.

여기에서 팀의 성과는 엔지니어의 속도에 엔지니어의 최소 효율성을 곱한 값입니다.

따라서 입력이 n =6, 속도 =[1,5,8,2,10,3], 효율 =[9,7,2,5,4,3], k =2인 경우 출력은 속도 10과 효율성 4의 엔지니어와 속도 5와 효율성 7의 엔지니어를 선택하여 팀의 최대 성능을 가지므로 60이 됩니다. 즉, 성능 =(10 + 5) * min(4, 7) =60입니다. .

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• ret :=0

• 하나의 2D 배열 정의 v

• initialize i :=0의 경우, i

  • v

    끝에 { e[i], s[i] } 삽입

• 배열 v를 역순으로 정렬

• 하나의 우선순위 큐 pq 정의

• 합계 :=0

• initialize i :=0의 경우, i

  • pq의 크기가 k와 같으면 -

    • sum :=sum의 최상위 요소 - pq

    • pq에서 요소 삭제

  • 합계 :=합계 + v[i, 1]

  • pq에 v[i, 1] 삽입

  • ret :=ret와 sum의 최대값 * v[i, 0]

• 리턴 모드(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