Hiệu suất tối đa của một nhóm trong C ++

Giả sử có n kỹ sư. Chúng được đánh số từ 1 đến n và chúng ta cũng có hai mảng:tốc độ và hiệu quả, ở đây tốc độ [i] và hiệu quả [i] đại diện cho tốc độ và hiệu quả của kỹ sư thứ i. Chúng tôi phải tìm ra hiệu suất tối đa của một nhóm bao gồm nhiều nhất k kỹ sư. Câu trả lời có thể rất lớn vì vậy hãy trả lại nó theo mô-đun 10 ^ 9 + 7.

Ở đây, hiệu suất của một nhóm là tổng tốc độ của các kỹ sư nhân với hiệu suất tối thiểu giữa các kỹ sư của họ.

Vì vậy, nếu đầu vào là n =6, tốc độ =[1,5,8,2.10,3], hiệu suất =[9,7,2,5,4,3], k =2, thì đầu ra sẽ là 60, vì chúng tôi có hiệu suất tối đa của nhóm bằng cách chọn kỹ sư có tốc độ 10 và hiệu suất 4 và kỹ sư có tốc độ 5 và hiệu suất 7. Nghĩa là, hiệu suất =(10 + 5) * min (4, 7) =60 .

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ret:=0

• Xác định một mảng 2D v

• để khởi tạo i:=0, khi i

  • chèn {e [i], s [i]} vào cuối v

• sắp xếp mảng v theo thứ tự ngược lại

• Xác định một hàng đợi ưu tiên pq

• tổng:=0

• để khởi tạo i:=0, khi i

  • nếu kích thước của pq bằng k, thì -

    • sum:=phần tử trên cùng của sum - pq

    • xóa phần tử khỏi pq

  • sum:=sum + v [i, 1]

  • chèn v [i, 1] vào pq

  • ret:=tối đa của ret và sum * v [i, 0]

• return ret mod (1 ^ 9 + 7)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

6, {1,5,8,2,10,3}, {9,7,2,5,4,3}, 2

Đầu ra

60