Computer >> Máy Tính >  >> Lập trình >> C ++

Công việc mang lại nhiều lợi nhuận nhất trong C ++

Giả sử chúng ta gặp khó khăn trong công việc [i] và mảng này cho biết độ khó của công việc thứ i và lợi nhuận [i] là lợi nhuận của công việc thứ i. Bây giờ hãy xem xét chúng tôi có một số công nhân. worker [i] là khả năng của công nhân thứ i, điều này có nghĩa là công nhân này chỉ có thể hoàn thành một công việc với độ khó nhiều nhất là công nhân [i]. Mỗi công nhân có thể làm nhiều nhất một công việc, nhưng một công việc có thể hoàn thành nhiều lần. Chúng ta phải tìm ra lợi nhuận cao nhất mà chúng ta có thể tạo ra là gì?

Ví dụ:nếu đầu vào là khó khăn =[2,4,6,8,10] và lợi nhuận =[10,20,30,40,50] và công nhân =[4,5,6,7], thì sản lượng sẽ là 100. Vì vậy, công nhân có thể được giao việc khó [4,4,6,6], và lợi nhuận thu được [20,20,30,30], tổng cộng là 100.

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

  • ans:=0 và n:=kích thước của mảng lợi nhuận
  • sắp xếp mảng worker
  • tạo danh sách các cặp được gọi là v
  • cho tôi trong phạm vi từ 0 đến n - 1,
    • chèn cặp (khó khăn [i], lợi nhuận [i]) vào v
  • sắp xếp mảng v
  • maxVal:=0, m:=kích thước của mảng worker và j:=0
  • cho tôi trong phạm vi từ 0 đến m - 1
    • while j
    • maxVal:=max của maxVal và giá trị thứ hai của v [j]
    • tăng j lên 1
  • ans:=ans + maxVal
  • trả lại ans

    • 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 maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
      int ans = 0;
      sort(worker.begin(), worker.end());
      vector < pair <int, int> > v;
      int n = profit.size(); // Number of jobs
      for(int i = 0; i < n; i++){
         v.push_back({difficulty[i], profit[i]});
      }
      sort(v.begin(), v.end());
      int maxVal = 0;
      int m = worker.size(); // Number of workers
      int j = 0;
      for(int i = 0; i < m; i++){
         while(j < n && v[j].first <= worker[i]){
            maxVal = max(maxVal, v[j].second);
            j++;
         }
         ans += maxVal;
      }
      return ans;
   }
};
int main() {
   Solution ob1;
   vector<int> difficulty{2,4,6,8,10};
   vector<int> profit{10,20,30,40,50};
   vector<int> worker{4,5,6,7};
   cout << ob1.maxProfitAssignment(difficulty, profit, worker) << endl;
   return 0;
}

    Đầu vào 

    [2,4,6,8,10]
[10,20,30,40,50]
[4,5,6,7]
vector<int> difficulty{2,4,6,8,10};
vector<int> profit{10,20,30,40,50};
vector<int> worker{4,5,6,7};

    Đầu ra 

    100