C++ में IPO समस्या

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

मान लीजिए हमारे पास कई प्रोजेक्ट्स हैं। प्रत्येक प्रोजेक्ट i के लिए, इसका एक शुद्ध लाभ Pi है और इसे शुरू करने के लिए न्यूनतम पूंजी Ci की आवश्यकता है। शुरू में हमारे पास W पूंजी है। जब हम एक प्रोजेक्ट पूरा करते हैं, तो हमें उसका शुद्ध लाभ मिलता है और वह लाभ हमारी कुल पूंजी में जुड़ जाता है।

संक्षेप में, दिए गए प्रोजेक्ट्स की सूची में से अधिकतम k अलग-अलग प्रोजेक्ट्स चुनें ताकि हमारी अंतिम पूंजी अधिकतम हो, और अंतिम अधिकतम पूंजी आउटपुट करें।

उदाहरण: k = 2, W = 0, Profits = [1,2,4], Capital = [0,1,1] → आउटपुट 5। क्योंकि शुरू में पूंजी 0 है, हम इंडेक्स 0 का प्रोजेक्ट शुरू कर सकते हैं, लाभ 1 मिलता है, पूंजी 1 हो जाती है। पूंजी 1 के साथ, हम इंडेक्स 1 या 2 का प्रोजेक्ट शुरू कर सकते हैं, हम इंडेक्स 2 चुनते हैं अधिक लाभ के लिए, अंतिम उत्तर 0 + 1 + 4 = 5।

समाधान दृष्टिकोण (दो प्रायोरिटी क्यू)

1. दो प्रायोरिटी क्यू बनाएं: pqCapital (कैपिटल के आधार पर मिन-हीप) और pqMain (प्रॉफिट के आधार पर मैक्स-हीप)।
2. n := Profits.size()।
3. सभी प्रोजेक्ट्स को {Profits[i], Capital[i]} के रूप में pqCapital में डालें।
4. i = 0 से k-1 तक k बार लूप करें:
   • जब pqCapital खाली नहीं है और टॉप एलिमेंट की कैपिटल ≤ W:
     • टॉप एलिमेंट को pqCapital से pqMain में मूव करें।
   • यदि pqMain खाली है, तो लूप से बाहर निकलें।
   • W := W + pqMain.top().first (सबसे अधिक लाभ वाला प्रोजेक्ट चुनें)।
   • pqMain से टॉप एलिमेंट हटाएं।
5. W लौटाएं।

C++ कार्यान्वयन

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

int main() {
    Solution ob;
    vector<int> profits = {1, 2, 4}, capital = {0, 1, 1};
    cout << ob.findMaximizedCapital(2, 0, profits, capital);
    return 0;
}

इनपुट

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

आउटपुट

5