C++ में IPO (Initial Public Offering)

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

मान लीजिए हमारे पास कई परियोजनाएं हैं। प्रत्येक परियोजना 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 := Profits का आकार
• i := 0 से प्रारंभ करें, जब i < n, i बढ़ाते हुए, करें -
  • { Profits[i], Capital[i] } को pqCapital में डालें
• i := 0 से प्रारंभ करें, जब i < k, i बढ़ाते हुए, करें -
  • जब (pqCapital खाली नहीं है और pqCapital के शीर्ष तत्व का दूसरा मान <= W), करें -
    • pqCapital के शीर्ष तत्व को pqMain में डालें
    • pqCapital से तत्व हटाएं
  • यदि 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