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
• {Profits [i]、Capital[i]}をpqCapitalに挿入

理解を深めるために、次の実装を見てみましょう-

例

#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