IPO bằng C ++

Giả sử một công ty A muốn bắt đầu IPO sớm. Để bán được giá tốt cổ phần của mình cho B, A muốn thực hiện một số dự án tăng vốn trước khi IPO. A có nguồn lực hạn chế, nó chỉ có thể hoàn thành tối đa k dự án khác biệt trước khi IPO. Bạn có thể giúp A bằng cách thiết kế cách tốt nhất để tối đa hóa tổng số vốn của mình sau khi hoàn thành ít nhất k dự án khác biệt không?

Giả sử chúng ta có một số dự án. Đối với mỗi dự án i, nó có một lợi nhuận thuần túy là Pi và số vốn tối thiểu là Ci là cần thiết để bắt đầu dự án tương ứng. Lúc đầu, chúng ta có W vốn. Khi chúng tôi hoàn thành một dự án, chúng tôi sẽ thu được lợi nhuận thuần túy và lợi nhuận sẽ được cộng vào tổng vốn của chúng tôi.

Để tổng hợp, hãy chọn một danh sách tối đa k dự án khác biệt từ danh sách dự án nhất định để tối đa hóa số vốn cuối cùng của chúng tôi và tạo ra số vốn tối đa cuối cùng.

Vì vậy, nếu đầu vào là - k =2, W =0, danh sách lợi nhuận giống như [1,2,4], vốn là [0,1,1], thì đầu ra sẽ là 5. Điều này là do, khi chúng ta có vốn 0 lúc đầu, vì vậy chúng tôi có thể bắt đầu dự án ở chỉ số 0, vì vậy chúng tôi có thể nhận được lợi nhuận 1, do đó vốn sẽ là 1. Với số vốn 1, chúng tôi có thể bắt đầu dự án ở chỉ số 1 hoặc 2, chúng tôi sẽ chọn dự án ở chỉ số 2 để thu được nhiều lợi nhuận hơn, vì vậy câu trả lời cuối cùng sẽ là 0 + 1 + 4 =5.

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

• Tạo hàng đợi ưu tiên pqCapital và pqMain
• n:=quy mô của Lợi nhuận
• để khởi tạo i:=0, khi i
• chèn {Profits [i], Capital [i]} vào pqCapital

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;
struct Comparator{
   bool operator() (pair <int, int> a, pair <int, int> b){
      return !(a.second < b.second);
   }
};
class Solution {
public:
   int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
   priority_queue < pair <int, int>, vector < pair <int, int> >, Comparator> pqCapital;
   priority_queue < pair <int ,int> > pqMain;
   int n = Profits.size();
   for(int i = 0; i < n; i++){
      pqCapital.push({Profits[i], Capital[i]});
   }
   for(int i = 0; i < k; i++){
      while(!pqCapital.empty() && pqCapital.top().second <= W){
         pqMain.push(pqCapital.top());
         pqCapital.pop();
      }
      if(pqMain.empty()) break;
         W += pqMain.top().first;
         pqMain.pop();
      }
      return W;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,4}, v1 = {0,1,1};
   cout << (ob.findMaximizedCapital(2,0, v, v1));
}

Đầu vào

2
0
[1,2,4]
[0,1,1]

Đầu ra

5