सी++ में आईपीओ

मान लीजिए कि एक कंपनी ए जल्द ही अपना आईपीओ शुरू करना चाहती है। बी को अपने शेयरों की अच्छी कीमत बेचने के लिए, ए आईपीओ से पहले अपनी पूंजी बढ़ाने के लिए कुछ परियोजनाओं पर काम करना चाहता है। A के पास सीमित संसाधन हैं, यह IPO से पहले केवल k विशिष्ट परियोजनाओं को पूरा कर सकता है। क्या आप अधिकतम k विशिष्ट परियोजनाओं को पूरा करने के बाद अपनी कुल पूंजी को अधिकतम करने का सबसे अच्छा तरीका तैयार करके A की मदद कर सकते हैं?

मान लीजिए कि हमारे पास कई परियोजनाएं हैं। प्रत्येक परियोजना के लिए, इसका शुद्ध लाभ पीआई है और संबंधित परियोजना को शुरू करने के लिए सीआई की न्यूनतम पूंजी की आवश्यकता है। सबसे पहले, हमारे पास 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 करें
• pqCapital में {Profits[i], Capital[i] } डालें

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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