C ++ IPO

假设一家公司A希望很快开始其IPO。为了以合理的价格向B出售股票，A希望从事一些项目，以在IPO前增加其资本。A的资源有限，在IPO前最多只能完成k个不同的项目。您可以通过设计最多最多k个不同项目后最大化其总资本的最佳方法来为A提供帮助吗？

假设我们有几个项目。对于每个项目i，它都有一个纯利润Pi，并且需要最小的Ci资本来启动相应的项目。首先，我们有W资本。当我们完成一个项目时，我们将获得其纯利润并将利润添加到我们的总资本中。

综上 ，从给定项目列表中选择最多k个不同项目的列表，以最大化我们的最终资本，并输出最终的最大化资本。

因此，如果输入像− k = 2，W = 0，利润表像[1,2,4]，资本是[0,1,1]，那么输出将是5。这是因为首先有资本0，所以我们可以从索引0开始项目，所以我们可以获得利润1，因此资本为1。有了资本1，我们可以从索引1或2开始项目，我们将选择索引2到获得更多利润，因此最终答案将是0 + 1 + 4 = 5。

为了解决这个问题，我们将遵循以下步骤-

• 创建优先级队列pqCapital和pqMain

• n：=利润大小

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• 将{Profits [i]，Capital [i]}插入pqCapital

• 对于初始化i：= 0，当i <k时，更新（将i增加1），执行-

• 从循环中出来

• 将pqCapital的top元素插入pqMain

• 从pqCapital删除元素

• 而（pqCapital不为空，并且pqCapital的top元素的第二个值<= W），则执行-

• 如果pqMain为空，则-

• W：= W + pqMain顶部元素的第一个值

• 从pqMain删除元素

• 返回W

让我们看下面的实现以更好地理解-

示例

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

输入值

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

输出结果

5